2667번: 단지번호 붙이기 (그래프, BFS)

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

# 단지번호 붙이기
# https://www.acmicpc.net/problem/2667 (그래프, BFS)

from collections import deque


def bfs(x, y, area):
    dq = deque([(x, y)])

    while dq:
        x, y = dq.popleft()
        if mp[x][y] == 0 or visited[x][y]:
            continue

        global count
        count += 1
        visited[x][y] = area

        direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for e in direction:
            nx, ny = x + e[0], y + e[1]
            if 0 <= nx < n and 0 <= ny < n and mp[nx][ny] == 1 and not visited[nx][ny]:
                dq.append([nx, ny])

    return count


n = int(input())
mp = [list(map(int, input())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]

area = 1
count_list = []
for num in range(n * n):
    i, j = num // n, num % n
    count = 0
    if bfs(i, j, area) > 0:
        area += 1
        count_list.append(count)

print(len(count_list))
print("\n".join(map(str, count_list)))