백준 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);
}

 

코드

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

N, M, R = map(int, input().split())
graph = [[] for i in range(N)]
visited = [0]*N
count = 1
for i in range(M):
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)

for i in range(N):
    graph[i].sort()

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

dfs(R-1)
for i in range(N):
    print(visited[i])

 

풀이

우선 DFS(깊이 우선 탐색)를 간단히 정의하자면, 그래프에서 한 점을 시작으로 다른 점들을 돌아다니면서 탐색하는데, 이때 한 줄기를 타고 끝까지 가보는 방식으로 탐색하는 것이다. 마치 광산에서 광맥을 찾으면 광맥이 끊길때까지 파다가 끊기면 다시 원래 있던 곳으로 돌아와서 새로운 광맥을 파는 것과 같다. DFS의 과정에 대해서는 따로 글을 써보겠다.

이름에서 알 수 있듯이, DFS는 그래프 안을 '탐색'하는 것으로, 그래프 안에서 특정한 점을 찾거나 그래프의 구조 파악 등 다른 목적으로 그래프 안을 샅샅이 돌아다닐 때 사용된다.

 

이를 코드로 구현해보자.

얼마나 깊이 들어갈지 모르는 상황에서 탐색 과정을 반복해야 하니 탐색 과정을 재귀함수로 구현해서 더이상 방문할 수 있는 점이 없을 때 더이상 재귀를 잇지 않고 return 하는 방법을 사용할 수 있을 것이다.

이때 한 점에서 갈 수 있는 점들이 여러 개 존재할때, 코드에서도 번호가 작은 점(위 문제가 요구하는 순서)에 먼저 방문하는 등으로 점들을 방문하는 순서를 정해줄 수 있다.

 

 

문제는 코드에서 자꾸 시간초과가 나오는 것이었다. 무엇이 문제인지 다른 블로그를 참고해보니, 다들 input = sys.stdin.readline라는 코드를 첫부분에 붙여두고 있었다. input의 형식을 바꿔주는듯 한데, 확실히 입력이 최대 100000번정도 있을 수 있으므로 이를 최적화해주는 것도 시간 절감에 큰 도움을 줄 것이다. 실제로 sys.stdin.readline은 input 함수에서 입력된 문자열 끝의 엔터(\n) 문자를 제거하는 과정, 사용자의 입력을 기다리는 prompt 문자를 출력하는 과정을 없애서 input 함수보다 더 빠르다.