[백준] 2667 단지 번호 붙이기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/2667
• 🔑 BFS
  • 지도를 돌면서 1을 만나면 bfs 실행한다.
  • 방문했으면 지도에 1을 0으로 바꾼다.
  • 이때 집의 수도 같이 센다.
  • 연결된 단지를 모두 탐색했으면 bfs 종료되고 단지 수를 올린다.

 

from collections import deque

n = int(input())

danji = [list(map(int, input())) for _ in range(n)]

total_danji = 0
danji_list = []

def bfs(i, j):
    mx, my = [0, 0, 1, -1], [1, -1, 0, 0]
    q = deque([(i, j)])
    danji[i][j] = 0

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

        for m in range(4):
            nx, ny = x + mx[m], y + my[m]

            if 0 <= nx < n and 0 <= ny < n and danji[nx][ny] == 1:
                q.append((nx, ny))
                danji[nx][ny] = 0
                cnt += 1
    return cnt

for i in range(n):
    for j in range(n):
        if danji[i][j] == 1:
            danji_list.append(bfs(i, j))
            total_danji += 1

danji_list.sort()
print(total_danji)
for i in danji_list: print(i)