[BOJ] 백준 2178 미로 탐색 (Swift)

문제

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

풀이

BFS를 사용하여 풀 수 있는 문제입니다.
BFS는 간선의 비용이 동일할 때, 최단 경로로 방문한다는 특징이 있습니다.

물론 DFS + 백트래킹을 사용하여 모든 경로를 구해 답을 구할 수는 있겠지만,
100 * 100 크기이고, 모든 수가 1로 되어있다는 등 최악의 경우를 고려하면 시간초과가 날 것입니다.

그래서 BFS로 접근하여 풀었습니다.

BFS 하면서 queue에 y, x 좌표와 얼마만큼 이동했는지 depth라는 변수를 두어서 확인했습니다.
queue의 y, x 좌표가 n - 1, m - 1이라면 도착이므로 depth를 출력해주었습니다.

도착을 못하는 경우는 없기 떄문에 고려하지 않아도 문제되지 않습니다.

소스코드

후기

간선의 비용이 동일하기 때문에, 최단 경로를 구하려면 BFS를 사용해야 했던 문제였습니다.