DFS BFS 카테고리에 해당하는 문제들을 풀고 있는데
자주 틀리는 부분이 있어서 DFS, BFS 정리와 오답 노트를 작성합니다.

흔히 있는 그래프 그림 말고 다른걸로 기록하고 싶어서 상황을 하나 만들겠습니다.

이사갈 집의 구조입니다.
거실에는 방 A, B, C가 연결되어 있고,
각각의 방에는 방A1, A2, A3...와 같이 방이름+번호 형식의 3개의 방이 이어져있다고 가정합니다.

방이 몇개있는지 확인하는 방법을 DFS와 BFS로 알아봅시다.

DFS

깊이 우선 탐색은 연결된 방이 없을때까지 진입해서 확인합니다.
거실에서 방A가 연결되어 있는것을 확인하자마자 방B, 방C는 보지 않고 방A에 들어갑니다.
이후 방A에 연결된 방A1을 확인합니다.

만약 방A1에 연결된 또 다른 방이 있다면 연결된 방이 없을때까지 계속 확인합니다.
A1, A2, A3를 확인하고 더 연결된방이 없으면 그 방을 나오고, 다음 방을 확인합니다.
이 때 역시 연결된 방이 없을때까지 들어가서 확인합니다.

거실 - 방A - 방A1 - 방A2- 방A3 - 방B - 방B1 - 방B2 - 방B3 - 방C - 방C1 - 방C2 - 방C3
순으로 방을 확인하게 됩니다.

DFS는 미로를 탈출할 때 쓰는 방법과 같습니다.
왼손으로 벽을 짚고 가다 보면 언젠가 미로를 탈출할 수 있게 됩니다.
출구를 찾을때까지 깊게 들어가는 이 방법이 깊이 우선 탐색입니다.

주로 스택과 재귀를 통해 구현하는데
DFS(거실) => DFS(방A) => DFS(방A1) ... 이런식으로 재귀를 통해 후입선출 스택처럼 동작하게 됩니다.

BFS

너비 우선 탐색은 연결된 방이 몇개인지부터 체크합니다.
거실에 들어가서 '방A, 방B, 방C가 있구나'를 생각하고
방A에 들어가서 '방A1, 방A2, 방C1가 있구나'를 생각합니다.

거실 - 방A - 방B - 방C - 방A1 - 방A2 - 방A3 - 방B1 - 방B2 - 방B3 - 방C1 - 방C2 - 방C3
순으로 방을 확인하게 됩니다.

주로 큐를 통해 구현되는데
[거실, 방A, 방B, 방C, ...]와 같이 선입선출 큐처럼 동작하게 됩니다.

BFS는 특정 위치까지의 최단 거리를 알 수 있습니다.
DFS는 방C2를 찾을때 방A부터 방문하므로 최악의 상황에서 오래 걸리는 반면,
BFS는 DFS에 비해 어느정도 평균적인 값을 보여줍니다.

오답노트

• 인접 행렬 (2차원 배열)로 문제를 풀 시 [x][y]인지 [y][x]인지 생각하자
• index가 그 값을 가리키는지 확인하자
  => 0을 사용하지 않고 index가 그 번째를 뜻하는 경우, 문제가 0 3 과 같이 입력을 줄 수도 있음
• 문제의 주의사항을 제대로 읽자