[BOJ] 백준 2178번 - 미로 탐색(with Java)

알고리즘

인접리스트를 사용해서 문제를 풀었던 [BOJ] 1260번 - DFS와 BFS와는 달리 2차원의 미로에서 최단거리를 찾기 위한 그래프 탐색은 조금 복잡하다. 우선 각각의 정점에 대한 행과 열 및 방문 여부를 표시하기 위해서 'Vertex' 클래스 생성해주고 문제풀이를 위한 배열들을 초기화하는 과정을 거쳐야한다.

 

이 문제는 위험부담이 있는 DFS와는 달리 효율이 좋은 BFS를 사용하여 풀기로 결정하였다. DFS는 최단거리를 한번에 찾는 경우에 최고의 효율을 보이지만, 그렇지 못하는 경우에는 백트래킹을 통해서 다른 경로를 재탐색해야하는 문제가 발생한다. 반면에 BFS는 그물망을 펼치는 것처럼 모든 경로를 넓지만 천천히 탐색하기 때문에 경로를 재탐색하는 문제가 발생하지 않는다. 따라서 이 문제의 경우에는 BFS를 사용하여 문제를 해결하기로 하였다.

 

시작 정점을 큐에 추가 및 방문됐음을 표시하는 것으로 BFS가 시작되며, 큐가 비어있을 때까지(더 이상 방문할 정점이 없을 때까지) 반복문이 수행된다. 조건문이 하나밖에 없던 [BOJ] 1260번 - DFS와 BFS 문제와는 달리 2차원의 평면에서는 상, 하, 좌, 우, 4가지 방향으로 이동할 수 있으므로 큐에서 반환된 순서대로 정답을 출력하는 방법은 사용할 수 없다. 따라서 각각의 정점에 대한 부모 배열을 만들어서 미로의 도착지점으로부터 부모 배열을 타고 올라가서 시작 정점을 찾는 방식으로 최단거리를 구하였다.

 

소스코드

문제링크

2178번: 미로 탐색