[BOJ] 단지번호붙이기(python)

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

사고 과정

• 그래프를 다 돌면서 1을 만났을 때 bfs 함수를 수행하게 하였다. 그리고 bfs 함수를 수행할 때 총 단지의 수를 세기 위해 cnt를 +1 해주었다.
• bfs 함수 내에서는 우선 1일 때 bfs가 수행되므로 처음에 아파트의 수인 cnt_apt를 +1 해주고 bfs를 수행하며 주변에 1인 곳(아파트가 있는 곳)이 있다면 cnt_apt에 +1을 해주었다.
• 마지막에는 총 단지의 수를 먼저 프린트해주고 각 단지내 집의 수를 오름차순으로 출력해주었다.

나의 풀이

from collections import deque
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))

result = []
def bfs(graph, a, b):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]


    global cnt_apt

    graph[a][b] = 0
    queue = deque()
    queue.append((a,b))
    cnt_apt+=1

    while queue:
        x, y = queue.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 graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
                cnt_apt += 1


cnt = 0

result = []
for a in range(n):
    for b in range(n):
        cnt_apt = 0
        if graph[a][b] == 1:
            bfs(graph, a, b)
            cnt += 1
            result.append(cnt_apt)
print(cnt)
for i in sorted(result):
    print(i)