[Python] 백준2667번 : 단지번호붙이기

💡문제

백준 2667번 문제 링크

🍀풀이

이 문제는 java로 한번 풀었던 문제인데, 이전에 풀었던 문제들과 비슷한 유형이다.
result 배열과 count = 0 변수를 선언해서 bfs가 한번 돌고 나면 count += 1 해서 총 단지수를 구하고, bfs 내에서 num += 1을 해줌으로써 각 단지내 집의 수를 구한다. 구한 각 단지내 집의 수를 result 배열에 넣고 오름차순 정렬해서 각 값들을 출력하는 식으로 풀었다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().rstrip())
graph = [list(map(int, input().rstrip())) for _ in range(n)]

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

result = []
count = 0

def bfs(x, y):
    graph[x][y] = 0
    queue = deque()
    queue.append([x, y])
    num = 1
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append([nx, ny])
                num += 1
    return num

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            result.append(bfs(i, j))
            count += 1
result.sort()
print(count)
for i in result:
    print(i)