[백준 24479 파이썬] 알고리즘 수업 - 깊이 우선 탐색 1 (실버 2, DFS)

알고리즘 유형 : DFS
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [0]*(N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def DFS(v, cnt):
    visited[v] = cnt
    
    tmp = 1
    for adj_node in sorted(graph[v]):
        if not visited[adj_node]:
            tmp += DFS(adj_node, cnt + tmp)
    
    return tmp

DFS(R, 1)
print(*visited[1:], sep="\n")

풀이 요약

1. DFS로 모든 노드를 순차적으로 탐색하되, 탐색 노드의 방문 순서를 기록해야하는 문제이다.

   이를 위해 DFS는 자신의 방문 순서를 매개변수로 받고, 인접 미방문 노드로 DFS를 재개하여 총 방문한 노드의 개수를 리턴하도록 정의했다. (개수에 자기 자신도 포함)

2. 인접 노드를 for문으로 돌면서, tmp에는 인접 노드를 돌 때마다 리턴 값을 받아서 다음 인접 노드의 방문 순서를 정하는데 활용해준다. (cnt+tmp)

   참고로 인접 노드는 오름차순으로 방문해야한다. (문제에서 제시한 조건)

배운 점, 어려웠던 점

• 방문 순서를 기록하는 아이디어를 구상하는게 핵심이었다. 만만치않은 문제였다.