#162 백준 파이썬 [2667] 단지번호붙이기 - BFS

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

 

#Solution

BFS로 2차원 배열 리스트에 근접한 같은 수를 알아내는 문제이다.

미로 문제를 약간 변형한 것이라 보면된다.

다음과 같은 알고리즘을따른다.

 

1) house[0][0]부터 house[N][N]까지, 하나씩 검사한다.

2-0) 0이 나올 경우 pass

2-1) 1이 나올 경우 상하좌우 인접한 모든 집을 구해준다.

3) BFS(너비 우선 탐색)를 이용해 인접한 노드를 구한다.

4) queue의 앞에서 부터 하나씩 pop하여 block과 visited 두 리스트에 추가해준다.

5) 상하좌우에 집이 있고, block과 queue에 없다면 해당 집을 queue에 추가해준다.

6) queue가 빌 때까지 계속해준다.

7) block의 길이와 visited를 return 해준다.

8) 출력 요구대로 출력한다.

#BFS로 단지 확인 알고리즘
def bfs(house, i, j, N, visited):
    
    if house[i][j] == 0: #0일 경우 함수를 넘김
        visited.append([i, j])
        return [0, visited] 
    
    block = [] #함수 안에서만 쓰일 블록
    queue = [[i, j]] #함수 안에서만 쓰일 큐
    
    while queue:
        [i, j] = queue.pop(0)
        block.append([i, j]) #블록에 쌓아줌
        visited.append([i, j]) #방문 리스트에 쌓아줌
        
        if house[i][j] == 1: #각각 상하좌우를 확인하는 조건문
            if i < N-1 and house[i+1][j] == 1 and [i+1, j] not in block and [i+1, j] not in queue:
                queue.append([i+1, j])
            if j < N-1 and house[i][j+1] == 1 and [i, j+1] not in block and [i, j+1] not in queue:
                queue.append([i, j+1])
            if j > 0 and house[i][j-1] == 1 and [i, j-1] not in block and [i, j-1] not in queue:
                queue.append([i, j-1])
            if i > 0 and house[i-1][j] == 1 and [i-1, j] not in block and [i-1, j] not in queue:
                queue.append([i-1, j])

    return [len(block), visited] #블록의 크기와, 방문한 노드들만 반환


N = int(input())
house = []
visited = []
result = []
for _ in range(N): #단지를 2차원 배열로 받음
    house.append(list(map(int, str(input()))))

#0,0 부터 N,N까지 각각의 노드에 관하여 함수 실행
for i in range(N):
    for j in range(N):
        if [i, j] not in visited:
            [size, visited] = bfs(house,i,j,N,visited)
            if size != 0: #1이 하나라도 포함된 사이즈 추가
                result.append(size) 

#출력문
print(len(result))
for i in sorted(result):
    print(i)