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

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

2667번: 단지번호붙이기

 

 

from collections import deque
def BFS(i, j):
    global matrix, cnt

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque([[i,j]])

    matrix[i][j] = 0
    count = 1
    while q:
        y, x = q.popleft()
        for i in range(4):

            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<N and 0<=ny<N and matrix[ny][nx]:
                q.append([ny, nx])
                matrix[ny][nx] = 0
                count += 1

    cnt.append(count)


N = int(input())
matrix = []
cnt = []
for i in range(N):
    matrix.append(list(map(int, input())))

for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            BFS(i,j)


print(len(cnt))
cnt.sort()
for c in cnt:
    print(c)