백준 - 알고리즘 수업 - 깊이 우선 탐색 1(24479번 Python 풀이)

이 문제는 알고리즘 유형 중 DFS를 통해 푸는 문제이다

 

깊이 우선 탐색(DFS, Depth-First Search)은 최대한 깊게 내려갔다가 더 이상 갈 수 없다면 다시 가장 가까운 갈림길로 돌아가 다른 방향을 탐색하는 깊이 우선 탐색 방식이다. 보통 스택 또는 재귀함수로 문제 풀이를 하며 모든 정점을 방문하거나 경로의 특징을 저장해야하는 문제는 DFS를 사용해 풀면 좋습니다.

 

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

n, m, r = map(int, input().split())

v=[0] * (n+1)
graph=[[] for i in range(n+1)]
cnt=1

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

def dfs(r):
	global cnt
	v[r] = cnt
	graph[r].sort()
	for x in graph[r]:
		if v[x] == 0:
			cnt+=1
			dfs(x)

dfs(r)
for i in range(1, n+1):
	print(v[i])

문제를 풀면서 계속 같은 오류가 발생했는데 알고보니 런타임 에러 (RecursionError)이 떴고 그 이유는 Python이 정한 재귀 깊이를 넘어서 그런 것이었고 이 문제 때문에 계속 오류가 났었다. 자세한 내용은 https://help.acmicpc.net/judge/rte/RecursionError 이 페이지를 참고하면 좋을 것 같다.

 

또한 이것의 풀이는 먼저 하나의 이차원 배열을 만들어준 뒤 각자 간선의 정보를 통해 갈 수 각 인덱스 번호에서 갈 수 있는 곳을 모두 넣어준다. 함수에서 오름차순으로 정렬을 해주고 각 정점에는 몇 번째 순서로 방문했는지 체크해주고 마지막에 출력을 합니다.