목차

TL; DR

  1. DFS 는 스택과 재귀를 이용한다.
  2. BFS 는 큐와 반복문을 이용한다.
  3. 문제에서 요구하는 조건에 따라 DFS 나 BFS 둘 중 하나를 선택한다.

본 게시물에서는 C언어로 코드를 작성했습니다.

또한, 자료구조(queue, stack)는 이미 구현했다는 가정 하에 작성했습니다.

C언어를 사용하신다면 해당 자료구조를 먼저 구현해보는 것을 권장드립니다.

미로찾기 알고리즘이란?

출처 : 교보문고

출처 : 교보문고

미로찾기 알고리즘은 코딩 테스트에서 자주 등장하는 알고리즘이다.

시작 지점과 도착 지점이 주어지며, 탈출할 수 있는 경로를 출력하거나 탈출까지 걸리는 최단 거리를 구할 수도 있다.

문제에 따라 DFS(Depth First Search)와 BFS(Breadth First Search) 를 적절하게 선택해서 해결할 수 있다.

각각의 해결 방법을 비유를 통해 비교한다면 다음과 같이 할 수 있을 것 같다.

컵 여러 개가 일렬로 있을 때, 컵에 물을 채우는 방식은 아래와 같다.