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

2667번: 단지번호붙이기

from collections import deque


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

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    apt[x][y] = 0
    cnt = 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx >= n or ny >= n or ny<0 or nx<0:
                continue
            if apt[nx][ny] == 1:
                cnt += 1
                apt[nx][ny] = 0
                queue.append((nx,ny))
               
    return cnt
       
ans = []
for i in range(n):
    for j in range(n):
        if apt[i][j] == 1:
            k = bfs(i,j)
            ans.append(k)
ans.sort()
print(len(ans),*ans,sep='\n')

# 반례 : 집이 하나인 경우는?
# 4
# 1000
# 0000
# 0111
# 0001