2667 단지번호붙이기

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

2667번: 단지번호붙이기

 

내 풀이(결국 구글링을 해서 이해했다ㅜㅜ)

from collections import deque

n = int(input())
ary = []
for i in range(n):
    ary.append(list(map(int, input())))
    
#상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    q = deque()
    q.append((x, y))
    ary[x][y] = 0
    count = 1
    
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue

            if ary[nx][ny] == 1:
                ary[nx][ny] = 0
                q.append((nx, ny))
                count += 1
    return count

chk = []
for i in range(n):
    for j in range(n):
        if ary[i][j] == 1:
            chk.append(bfs(i, j))

chk.sort()
print(len(chk))
for i in chk:
    print(i)

bfs 알고리즘은 알고있었다. 하지만 함수 시작쯤에 ary[x][y] = 0으로 처리하고 count의 수를 1 올리는 것을 생각하지 못했다. ary[x][y]를 0으로 하는게 중요한 이유는 맨 처음에 들어온 좌표를 들렸다 치고 count를 1로 만들었기 때문이다.

그리고 한 bfs가 끝나면 count를 chk에 저장하여 단지 수 별로 저장해줬다.