백준. 2667번. 단지번호붙이기 파이썬 풀이

백준. 2667번. 단지번호붙이기 파이썬 풀이

문제링크 https://www.acmicpc.net/problem/2667

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10**6)

from collections import deque

# 지도의 크기, 정사각형임
n = int(input())

graph = []

for _ in range(n):
    graph.append(list(input()))


# 상하좌우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def bfs(Y, X):
    global graph
    global result
    count = 1

    Y = int(Y)
    X = int(X)

    queue = deque()
    queue.append([Y, X])
    graph[Y][X] = '-1'

    while queue:
        now_y, now_x = queue.popleft()
        for i in range(4):
            ny = int(now_y + dy[i])
            nx = int(now_x + dx[i])
            if 0 <= ny < n and 0 <= nx < n:
                if graph[ny][nx] == '1':
                    queue.append([ny, nx])
                    count += 1
                    graph[ny][nx] = '-1'

    result.append(count)



num = 0
result = []


for y in range(n):
    for x in range(n):
        if graph[y][x] == '1':
            num += 1
            bfs(y, x)

print(num)

result.sort()

for t in result:
    print(t)