[백준/알고리즘] #2667: 단지붙이기 [파이썬(python)/DFS/BFS]

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

2667번: 단지번호붙이기

 

DFS/BFS를 이용해서 각각의 기준점 별 거리계산하는 문제다.

 

문제에 "오름차순으로 정렬하여 출력"을 제대로 못 봐서 첫시도에 틀렸다.

문제를 똑바로 잘 읽자! ^^

 

dfs와 bfs 둘다 이용하여 풀어보았다.

bfs는 큐를 두고 좌표로 이동하며 카운트하고

dfs는 카운트를 글로벌 변수로 두고 재귀로 풀이하였다.

 

이런 문제에서는 둘 다 수행시간이 비슷한가보다.

 

파이썬 코드

#2667_단지번호붙이기_DFS/BFS
import sys
from collections import deque

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def dfs(x,y):
    
    if 0<= x < N and 0 <= y < N:
        if compx[x][y]==1 and compx[x][y]!=0:
            global cnt
            cnt+=1
            compx[x][y]=0
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                dfs(nx,ny)
            return True
    return False
cnt=0

                    
def bfs(x,y,house):
    q = deque()
    q.append((x,y))
    compx[x][y]=0
    cnt=0

    while q:
        x,y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<= nx < N and 0 <= ny < N:
                if compx[nx][ny]==house and compx[nx][ny]!=0:
                    q.append((nx,ny))
                    cnt+=1
                    compx[nx][ny]=0
    return cnt+1

N = int(input())
compx=[]
for _ in range(N):
    compx.append(list(map(int, input())))


house_cnt=[]
'''
for i in range(N):
    for j in range(N):
        if compx[i][j]==1:
            house_cnt.append(bfs(i,j,compx[i][j]))
            '''
for i in range(N):
    for j in range(N):
        if dfs(i,j)==True:
            house_cnt.append(cnt)
            cnt=0
print(len(house_cnt))

house_cnt.sort()
for i in house_cnt:
    print(i)

저 코드 그대로는 dfs로 풀이한다. 

주석친 for문을 풀고 그 바로 아래 for문을 주석 치면 dfs가 아닌 bfs 함수를 호출해서 풀이한다. 

 

bfs 풀이 : 96ms

dfs 풀이 : 96ms

 

같은 실행시간이 나왔다.