파이썬 백순 2667 단지번호붙이기

import sys
input = sys.stdin.readline
from collections import deque
 
n = int(input())
T = []
gone = {}
for i in range(n) : 
    T.append(list(input()))
    for j in range(n) : 
        gone[(i, j)] = False
T.append([None for i in range(n + 1)])
 
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def BFS(X, Y) : 
    que = deque()
    que.append([X, Y])
    gone[(X, Y)] = True
    count = 1
    while que : 
        a, b = que.popleft()
        for i in range(4) : 
            x = a + dx[i]
            y = b + dy[i]
            if T[x][y] == '1' and not gone[(x, y)] : 
                gone[(x, y)] = True
                count = count + 1
                que.append([x, y])
    return count
 
ans = []
for i in range(n) : 
    for j in range(n) : 
        if T[i][j] == '1' and not gone[(i, j)] : 
            ans.append(BFS(i, j))
ans.sort()
print(len(ans))
for i in ans : 
    print(i)

인접 영역의 갯수를 세는 문제이다.

실행하면 연결된 모든 영역에 방문기록을 남기는 BFS를 정의한다.

이때 영역의 크기도 출력해야 하므로, 연결된 곳으로 확산할 때마다 count를 세어 리턴으로 내보낸다.

모든 점에 대해 for문을 돌리며, 아직 방문기록이 없는 곳이라면 BFS를 실행하며 count를 ans에 저장한다.

ans의 길이가 영역의 갯수이고, ans의 원소가 각 영역의 크기이니 이를 출력한다.