풀이
[0][0]
에서 [n-1][m-1]
좌표까지의 최단거리 문제이기 때문에 BFS 를 활용했다.
이제 기본적인 BFS 구조는 이해했고 다양한 방면에서 활용할 수 있다.
”아기상어” 문제에서 활용했던 dist 배열을 통해 미로를 탐색하면서 각 좌표별 시작점부터의 거리를 저장하도록 코드를 작성했다.
시작점에서 BFS 를 실행시켜 모든 탐색이 끝난 후 dist[n-1][m-1]
을 반환하여 최단거리를 계산할 수 있다.
소스코드
References