2022.02.13 [백준] (python 파이썬) 단지번호붙이기

 

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

풀이

bfs풀이 방식입니다. 2중 for문을 돌려 arr배열에 값이 1인 곳을 찾고 찾은 곳부터 bfs탐색을 합니다. bfs탐색이 끝나면 마을 1개가 생기게 됩니다. bfs함수를 돌때 deq에 데이터가 추가 될때마다 cnt를 1씩 더해줘서 한 마을의 총 집의 개수를 세주고 이 갯수를 ans배열에 담은 후, 모든 계산이 끝난 후 배열을 sort로 정렬하여 출력합니다.

from collections import deque
 
n=int(input())
arr=[]
ans=[]
dx=[0,0,1,-1]
dy=[1,-1,0,0]
 
for _ in range(n):
    arr.append(list(map(int,input())))
 
def bfs(x,y):
    cnt=1
    deq=deque()
    deq.append([x,y])
    while deq:
        x,y=deq.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<n and arr[nx][ny]==1:
                deq.append([nx,ny])
                arr[nx][ny]=0
                cnt+=1
    ans.append(cnt)
 
num=0
for i in range(n):
    for j in range(n):
        if arr[i][j]==1:
            arr[i][j]=0
            bfs(i,j)
            num+=1
ans.sort()
print(num)
for i in ans:
    print(i)

 

아래의 코드는 dfs로 해결한 코드입니다. bfs코드에서 큐를 재귀로 사용했습니다. 

n=int(input())
arr=[]
ans=[]
 
dx=[0,0,1,-1]
dy=[1,-1,0,0]
 
def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=n:
        return False
    if arr[x][y]==1:
        global count
        count+=1
        arr[x][y]=0
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            dfs(nx,ny)
        return True
    return False
 
count=0
 
for _ in range(n):
    arr.append(list(map(int,input())))
for i in range(n):
    for j in range(n):
        if dfs(i,j)==True:
            ans.append(count)
            count=0
ans.sort()
print(len(ans))
for i in ans:
    print(i)