백준 2667 - BFS

백준 2667번 문제 해결 코드입니다. (https://www.acmicpc.net/problem/2667)

python으로 작성되었습니다.

해당 문제는 bfs의 대표적인 기초 연습문제 중 하나라고 생각합니다.

아파트 단지의 갯 수와 아파트 개수를 출력하는 문제 입니다.

아이디어는 다음과 같습니다.

1. 0,0 탐색시작
   2. 제자리, 상, 하, 좌, 우 5곳 탐색 만약 1발견 시 queue 삽입. graph의 해당 노드는 -1처리
   3. queue가 empty가 될때까지 1의 발견 갯수를 count하며 진행.
   ( 이 경우 하나의 단지를 모두 탐색 or 0,0이 0으로 둘러 쌓인 경우 탈출 )
2. 단지수 1 증가
3. graph의 1이 존재하는가 ( 방문하지 않는 노드가 있다면 )
4. 존재하는 경우 해당 노드 queue 삽입
5. 존재하지 않는 경우 return 단지 수, 단지들의 아파트 개수

from collections import deque

n = int(input()) 
graph = [] # input graph

for i in range(n):
    graph.append( [int(j) for j in input() ]) 
dx = [0,1,-1,0,0] # 제자리, 동, 서 ,남 북
dy = [0,0,0,1,-1]

def bfs(graph, n):  
    queue = deque() # for bfs
    result = [] 
    queue.append( [0,0] )
    cmplex = 0 # 아파트 단지
    while(True):
        count = 0  # 단지 내 아파트 수
        while(queue): 
            node = queue.pop()
            for i in range(5): # 제자리 상 하 좌우 
                x = node[0] + dx[i]
                y = node[1] + dy[i]
                if ( x < 0 or x >= n or y < 0 or y >= n): # 그래프 밖에 나간 경우
                    continue
                elif ( graph[x][y] == 0): #벽
                    continue
                elif ( graph[x][y] == -1): # 들린곳
                    continue
                else:
                    graph[x][y] = -1 # 들린 곳 처리
                    count += 1 # 집의 개수
                    queue.append([x,y]) # 다음에 방문 할 노드 
                    
        if (count != 0): # 탐색에서 아파트가 1개라도 발견된 경우.
            cmplex += 1 # 단지수 1개 추가 
            result.append(count) # 집의 개수 입력
        
        check = False
        for i in range(n):
            if ( check):
                break
            for j in range(n):
                if ( graph[i][j] == 1): #안들린 곳이 존재한다면 ( 다른 단지가 존재한다면 )
                    queue.append( [i,j] )# queue 삽입
                    check = True # 루프 탈출 
                    break
        if (not check): #  안들린 곳이 없다면 return
            if  (cmplex == 0 ): 
                return 0, [0] # 단지 수가 0인경우는 result가 null이므로 0을 추가해야한다.
            else:
                return cmplex, result
                        
cmplex, result = bfs( graph, n)
result.sort()


print(cmplex)
for i in result:
    print(i)

틀린이유 1, 2: 모두 0인 input을 놓쳤다.