궤도

문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바로 아래, 오른쪽에 있는 좌표까지의 최단거리는 2일 것이다. 그 다음엔 이렇게 되고, 계속 하다보면... 이렇게 최단거리를 찾았다. 지금 이 과정은 bfs로 한거나 다름없다. 왜냐하면 시작점(1, 1)에 대해 갈 수 있는 좌표((2, 1), (1, 2))를 큐에 넣었고 최단거리가 2인 좌표들을 순서대로 방문하며 갈 수 있는 좌표((3, 1), (2, 2), (1, 3))를 큐에 넣어 또다시 순서대로 해당 좌표들을 방문하며 진행했기 때문이다. 그럼 왜 dfs는 안될까? 그림을 통한 설명을 하기 전 간단하게 말하자면 dfs는..