문제

오늘도 서준이는 깊이 우선 탐색(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);
}

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

풀이

처음에는 인접행렬과 dfs재귀를 활용하여 문제를 풀었다. 인접행렬이 그래프관계를 나타냈을 때, 가장 직관적이고 재귀구조는 dfs 문제를 풀 때 가장 일반적인 풀이였기 때문이다. 그러나 인접행렬은 공간복잡도가 O(N^2)로 메모리를 많이 차지하여 메모리 초과 문제가 발생한다. 그리고 재귀로 풀었을 때 시간초과문제가 발생했다. 그래서 인접행렬을 인접리스트로 변경했고, 재귀를 stack을 활용한 반복문으로 바꿔서 풀었다.
간선의 가중치가 모두 동일하고 오름차순으로 방문해야하기 때문에 인접리스트를 정렬해준다. 단 stack구조를 사용하고 있고 마지막 원소가 먼저 pop되기 때문에 reverse=True 옵션을 주어 역순으로 정렬해준다. order변수를 활용해 방문순서를 지정해주면서 순회해주면 문제는 간단하게 해결된다.

import sys
from collections import deque

# 0번째 인덱스는 더미 인덱스로 사용
N, M, R = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    src, dst = map(int, sys.stdin.readline().split())
    adj[src].append(dst)
    adj[dst].append(src)
for x in range(1, N+1):
    adj[x] = sorted(adj[x], reverse = True)

visited = [0] * (N+1)
nodes_cnt = [0] * (N+1)
order = 1  # 방문순서 체크 변수
stack = deque()
stack.append(R)


while stack:
    cur_node = stack.pop()
    visited[cur_node] = 1
    if nodes_cnt[cur_node] == 0:
        nodes_cnt[cur_node] = order
        order += 1

    for next_node in adj[cur_node]:
        if visited[next_node] == 0:
            stack.append(next_node)

print(*nodes_cnt[1:])

어렵지 않은 문제이지만, 워낙 알고리즘을 오랜만에 풀다보니 메모리 초과 시간초과, 런타임에러를 모두 겪었다. 이를 해결하기위해 재귀가 아닌 반복문을 통해 풀려고하니 익숙치 않아 생각보다 오래걸렸다.