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

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

지도를 입력받아 단지마다 번호를 붙이는 문제이다.

dfs를 이용하여 구현하였다.!

n = int(input())

graph = []
result = []

for _ in range(n):
    row = list(map(int, input()))
    graph.append(row)

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

cnt = 0

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    
    if graph[x][y] == 1:
        global cnt
        cnt += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)
        return True
    return False

for i in range(n):
    for j in range(n):
        if dfs(i, j):
            result.append(cnt)
            cnt = 0

result.sort()

print(len(result))
for i in result:
    print(i)
    

단지내의 집의 수를 카운트하기 위해 cnt를 사용하였다.
dfs 재귀가 유지되는 범위내에서 graph[x][y]==1 일때 cnt가 1씩 증가한다.
집의수가 카운트 되는 것이다. 이것을 result에 append 시키는 방식이다.
dfs가 종료되는 시점에서 cnt=0 으로 초기화를 시켜주면, 다음 dfs가 실행될 때 다시 새로운 단지의 집의 수가 카운트 된다.

특이한 점은 집을 방문할 때 마다 graph=0으로 바꾸어준다는 것이다.

만약에 graph를 재사용해야하는 문제가 나왔을 때는, 우리가 흔히 푸는것처럼 visited를 만들어 따로 관리해주어야겠다는 것을 느꼈다.