문제
정점 N개, 간선 M개인 무방향 그래프를 입력받아 DFS와 BFS 탐색 순서를 출력하는 문제다. 방문할 수 있는 정점이 여러 개이면 번호가 작은 것부터 방문한다.
핵심 포인트
- 인접 리스트를 오름차순 정렬해두면 자연스럽게 번호가 작은 정점부터 탐색된다.
- DFS는 재귀(스택), BFS는
collections.deque(큐)를 사용한다. visited배열로 중복 방문을 방지한다.
Python 풀이
from collections import deque
import sys
input = sys.stdin.readline
def dfs(graph, v, visited, result):
visited[v] = True
result.append(v)
for next_v in graph[v]:
if not visited[next_v]:
dfs(graph, next_v, visited, result)
def bfs(graph, start, n):
visited = [False] * (n + 1)
visited[start] = True
queue = deque([start])
result = []
while queue:
v = queue.popleft()
result.append(v)
for next_v in graph[v]:
if not visited[next_v]:
visited[next_v] = True
queue.append(next_v)
return result
def main():
n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# 번호가 작은 것부터 방문하도록 정렬
for i in range(1, n + 1):
graph[i].sort()
# DFS
visited = [False] * (n + 1)
dfs_result = []
dfs(graph, v, visited, dfs_result)
print(*dfs_result)
# BFS
bfs_result = bfs(graph, v, n)
print(*bfs_result)
main()
Kotlin 풀이
import java.util.*
val graph = Array(1001) { mutableListOf<Int>() }
val visitedDfs = BooleanArray(1001)
val dfsResult = mutableListOf<Int>()
fun dfs(v: Int) {
visitedDfs[v] = true
dfsResult.add(v)
for (next in graph[v]) {
if (!visitedDfs[next]) dfs(next)
}
}
fun bfs(start: Int): List<Int> {
val visited = BooleanArray(1001)
val queue: Queue<Int> = LinkedList()
val result = mutableListOf<Int>()
queue.add(start)
visited[start] = true
while (queue.isNotEmpty()) {
val v = queue.poll()
result.add(v)
for (next in graph[v]) {
if (!visited[next]) {
visited[next] = true
queue.add(next)
}
}
}
return result
}
fun main() {
val br = System.`in`.bufferedReader()
val (n, m, v) = br.readLine().split(" ").map { it.toInt() }
repeat(m) {
val (a, b) = br.readLine().split(" ").map { it.toInt() }
graph[a].add(b)
graph[b].add(a)
}
for (i in 1..n) graph[i].sort()
dfs(v)
println(dfsResult.joinToString(" "))
println(bfs(v).joinToString(" "))
}
주의사항
재귀 깊이 제한: Python의 기본 재귀 제한은 1000이다. 정점이 많은 경우 sys.setrecursionlimit()으로 늘려야 한다.
import sys
sys.setrecursionlimit(10000)
Kotlin은 기본 스택 크기가 더 크기 때문에 이 문제에서는 문제없지만, 스택 오버플로우가 걱정되면 재귀 대신 명시적 스택을 사용하는 반복 DFS가 안전하다.
복잡도
- 시간: O(N + M) — 각 정점과 간선을 한 번씩 방문
- 공간: O(N + M) — 인접 리스트 + visited 배열
DFS/BFS는 대부분의 그래프 문제의 기초이므로 손으로 한 번씩 탐색 순서를 따라가 보는 편이 좋다.
DFS는 한 경로를 끝까지 따라가고, BFS는 시작점에서 가까운 정점부터 층별로 방문한다.
댓글