📒 깊이/너비 우선 탐색(DFS/BFS)

📌 사전지식

1. 그래프(graphs)
   • 정점(vertex, node)과 간선(edge, link)
   • 유향(directed)그래프와 무향(undirected)그래프
2. 스택(stack)
3. 큐(queue)

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

한 정점에서 인접한 모든(방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로
깊이 우선 탐색을 끝낸 후 다음 정점으로 진행한다.

진행 순서
0 -> 1 -> 3 -> 7 -> 4 -> 5 -> 2 -> 6

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

📑문제 응용 - Lv.3 여행경로

• 한 번에 진행
  -> 이것이 가능함은 문제에서 보장되어 있다.
• 시작 정점은 언제나"ICN"
• 모든 정점 방문이 아니고, 모든 간선을 거쳐야한다.
  -> 언젠가는 한 번 가야 하는데 그 순서를 결정해야 한다.
• 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우
  -> 공항 이름의 알파벳 순서를 따른다.

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

한 정점에서 인접한 모든(방문하지 않은) 정점을 방문하고, 방문한 각 인접 정점을
기준으로(방문한 순서에 따라) 또다시 너비 우선 탐색을 진행한다.

진행 순서
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행한다.