[24479] 알고리즘 수업 - 깊이 우선 탐색 1 - Python

/* 문제 */
오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.
dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  
    visited[R] <- YES; # 시작 정점 R을 방문 했다고 표시한다.  
    for each x ∈ E(R) # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
        if (visited[x] = NO) then dfs(V, E, x);
}

DFS 문제다. 주의할 점은 방문한 순서대로 노드들을 출력하는 것이 아니라 각 노드의 출력 순서를 출력해야 한다는 것이다.

기본적인 문제지만 DFS 문제를 처음 풀어보다 보니 여러 번 실패했다. 

 

1. [[ ]] * (n + 1)형식으로 리스트를 선언

graph = [[]] * (n + 1)	# [[], [], ... []]
graph[1].append[1]	# [[1], [1], ... [1]]

처음에는 그래프를 저장하기 위해 위와 같이 graph를 선언하고 입력 줄마다 append하려고 했다. 그러나 이 방식으로 2차원 리스트를 선언한 후 특정 요소에 값을 append하면 모든 요소에 같은 값이 추가되는 문제가 있었다.

graph = [[] for _ in range(n+1)]

그래서 위와 같이 list comprehension을 사용해 선언하니 원하는 대로 톱니형 리스트를 만들 수 있었다.

 

2. RecursionError

재귀 함수를 사용하는 DFS 문제를 파이썬으로 풀 때는 최대 재귀 깊이를 설정해 줘야 한다. 기본적으로 정해지는 최대 재귀 깊이는 (백준 기준) 1000으로 매우 낮기 때문에 그냥 문제를 풀면 RecursonError가 뜬다.

import sys
sys.setrecursionlimit(10**9)

따라서 위와 같이 최대 재귀 깊이를 크게 설정해준다.

 

3. input() 사용

반복문으로 여러 줄을 입력받을 때 모두 input()을 사용하면 시간 초과가 날 수 있다. 이럴 경우 시간 초과가 뜬다.

input = sys.stdin.readline

기존 input으로 입력받았던 코드는 그대로 두고 위의 코드를 추가해 해결했다.

 

# 정답 코드

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

def dfs(graph, v, visited):
    global count
    visited[v] = count
    count += 1
    for i in graph[v]:
        if visited[i] == 0:
            dfs(graph, i, visited)

n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n + 1)
count = 1

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
for i in graph:
    i.sort()

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

보통은 visited를 boolean 배열로 선언해 방문 여부를 저장하지만 이 문제에서는 정수로 방문 순서를 저장했다.