1. 오늘의 문제
오늘 문제는 깊이우선탐색에 대한 내용이었다.
깊이우선탐색을 배우긴 했으나 문제로 풀어보는 것은 처음!
https://www.acmicpc.net/problem/24479
오늘도 서준이는 깊이 우선 탐색(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);
}
2. 알고리즘
깊이우선탐색이란, 탐색을 할 때 깊이를 우선적으로 탐색하는 것이다.
여러 노드들이 있을 때, 노드의 끝까지 일단 가본다고 생각하면 된다.
백준에서 예시1로 주어진 내용을 한번 추상화 시켜보자.
5 5 1 //5개의 노드, 5개의 간선, 시작은 1에서
1 4 // 1과 4가 연결
1 2 // 1과 2가 연결
2 3 // 2와 3이 연결
2 4 // 2와 4가 연결
3 4 // 3과 4가 연결
이렇게 위의 그림처럼 그릴 수 있다.
깊이 우선 탐색의 순서는 아래와 같다.
- 1에서 하위 노드는 [2, 4] 가 있다. 이 중에서 2로 이동한다.
- 2에서 하위 노드는 [1, 3, 4] 이 있다. 1은 이미 방문하였으므로 제외하고, [3, 4] 중 작은 숫자인 3을 먼저 방문한다.
- 3에서 하위 노드는 [2, 4] 가 있다. 2는 이미 방문하였으니 제외하고 4를 방문한다.
- 5는 연결된 노드가 없으므로 방문할 수 없다.
- 따라서 각 노드에서의 방문순서를 표시하면 [1, 2, 3, 4, 0] 이 된다.
문제는 이것을 어떻게 구현할 것인가이다.
3. 해법
먼저 모두 0으로 만들어진 visited라는 리스트와 해당 노드들이 연결된 방식을 리스트로 만든다.
그리고 노드를 돌면서 방문한 노드에 해당하는 자리의 숫자를 바꿔주는 식으로 해보았다.
예를들어 3번째 노드를 3번째에 방문했다면, visited[3] = 3으로 바꿔주는 식이다.
그런데 방문의 순서를 결정하는 것이 정말 어려웠는데, 그건 stack으로 해결해 보았다.
1) 만일 첫번째로 1을 첫번째로 방문한다면, 1을 stack에 집어 넣는다. 그리고 visited에서 해당 자리를 1로 변경한다.
2) 그리고 다음 경로를 찾을 때, 기존에 있던 1을 제거하고 2의 하위노드들 중 큰 숫자부터 stack에 집어 넣는다.
3) 그리고 stack의 가장 마지막에 있는 노드를 탐색하고 visited를 변경해준다.
4) stack에서 제일 마지막에 넣은 2를 제거한 뒤, 2와 연결된 노드들 중 1은 이미 방문했으므로 [3, 4]를 뒤집어서 넣어준다.
5) 위와 같은 과정을 반복한다. 3에 방문한 뒤 visited[3]=3을 하고 stack에서 제거한다. 3과 연결된 노드가 [2,4] 이지만 2는 이미 방문했으므로 4만 stack에 추가한다.
6) 4에 방문한 뒤 4와 visited[4]=4로 변경하고, 연결된 경로를 stack에 추가하려고 해도 이미 모두 방문한 경로이다. 또한 stack에 들어있는 노드는 모두 방문한 노드만 남아 있기에, 이를 하나씩 삭제하면 stack이 비게 된다. 이 때가 탐색을 멈추는 순간이다.
4. 코드
위의 내용을 그대로 코드로 구현해 보았다.
from sys import stdin
put = stdin.readline
# 노드 수, 간선의 수, 시작 숫자를 입력 받음
v, e, s = map(int, put().split())
# 방문 여부를 표시하기 위한 리스트와 각 연결을 확인하기 위한 리스트를 만듦
visited = [0 for x in range(v+1)]
line = [[] for x in range(v+1)]
# 노드의 수만큼 for문을 돌면서 입력 받음.
# 입력 받은 자료에서 연결을 각각의 리스트에 저장
for i in range(e):
n, f = map(int, put().split())
line[n].append(f)
line[f].append(n)
# 리스트를 정렬하고 뒤집어 줌
# 뒤집는건 스택에 넣을 때 숫자가 큰게 아래쪽에 있기 위함
for l in line:
l.sort()
l.reverse()
# 검색을 위한 스택. 일단 시작 숫자를 넣어줌
# order는 방문 횟수를 기록하기 위함
stack = []
stack.append(s)
order = 0
# 스택이 비지 않는 한 계속 루프를 돈다.
while stack:
# 타겟은 스택의 제일 마지막.
target = stack[-1]
# 스택에서 제거하고 visited에 order를 남긴다.
# 만일 visited에서 0이 아니면 방문한거니 그냥 넘어간다.
stack.pop()
if visited[target] != 0:
continue
order += 1
visited[target]=order
# 해당 노드를 전개해서 스택에 집어넣는다.
for node in line[target]:
stack.append(node)
# visited에 내용을 출력한다.
for v in visited[1:]:
print(v)
5. 느낀점
처음에는 재귀함수를 이용해 짧고 간결하게 구현하려고 했으나 탐색의 깊이가 깊어지자 스택오버플로우로 인해 런타임에러가 발생했다.
재귀 함수를 사용할 때는 반드시 탐색의 깊이를 확인해보고, 깊이가 깊다면 스택이나 다른 방법을 이용해야 할 것 같다.
알고리즘을 구현해 볼 수 있어 즐거운 하루였다.
