[백준 - Python] 2667. 단지 번호 붙이기 (DFS/BFS)

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

2667번: 단지번호붙이기

 

코드

import sys
sys.setrecursionlimit(10**6)

n = int(input())
mat = [[] for _ in range(n)]
for i in range(n):
    row = input()
    for r in row:
        mat[i].append(int(r))

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

result = []
cnt = 1

def dfs(x, y):
    global cnt   # 개수 세는 변수 전역화
    mat[x][y] = 0
    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 mat[nx][ny] == 1:
            cnt += 1
            dfs(nx, ny)
            mat[nx][ny] = 0


for i in range(n):
    for j in range(n):
        if mat[i][j] == 1:
            dfs(i, j)
            result.append(cnt)
            cnt = 1  # dfs 한 번 끝나면 값 저장 후 초기화

l = len(result)
print(l)
result.sort()
for r in result:
    print(r)

 

해당 문제는 연결 요소의 개수를 구하는 보통의 문제와 동일한 유형이었지만,

한 가지 다른 점이라 하면,

각 연결 요소 별 노드의 개수를 출력해야 하는 점이 조금 달랐다.

 

각 연결 요소 별 노드의 개수를 세어주기 위해,

DFS 내에서 노드 개수를 세어주는 cnt 변수를 전역화하여 사용하였고

dfs가 한 번 끝날 때마다 카운팅 된 값을 저장하고

새로 초기화 해 주었다.