배경지식

그래프 (graphs)

• 정점 (vertex, node)와 간선 (edge, link)으로 이루어짐
• 유향 (directed) 그래프와 무향 (undirected) 그래프
• 스택
• 큐

깊이 우선 탐색 (DFS; Depth-First Search)

(빨간 숫자가 방문 순서)

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되,

각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후

다음 정점으로 진행하는 방식

스택을 이용하여 어느 정점에서 DFS를 하고 있는지 기억하고 되돌아감

너비 우선 탐색 (BFS; Breadth-First Search)

한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고,