[programmers][찾아라 프로그래밍 마에스터] 게임 맵 최단거리

문제 : programmers.co.kr/learn/courses/30/lessons/1844

---

0과 1로 이루어진 게임 맵이 2차원 배열로 주어진다. 0은 벽, 1은 통로를 의미한다.

시작 위치에서 종료지점으로 가고자 할 때 최단거리를 구해라. 종료지점으로 갈 수 없다면 -1을 반환해라.

---

전형적인 BFS 문제.

시작 지점에서 상하좌우((-1,0), (1,0),(0,-1),(0,1))로 이동하면서 이동횟수를 저장한다. 이동한 위치가 벽(0)이라면 탐색을 종료하고 통로(1)라면 해당위치에서 상하좌우로 탐색을 계속한다.

너비우선탐색으로 탐색하며 가장 먼저 도착지 (n, m)에 도착했을 때 이동횟수가 정답이 된다.

(n,m)에 도착하지 않고 탐색이 종료되었다면 -1을 반환한다.

 

시간복잡도는 게임맵 크기인 O(NM).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%B0%BE%EC%95%84%EB%9D%BC%20%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EB%A7%88%EC%97%90%EC%8A%A4%ED%84%B0/%EA%B2%8C%EC%9E%84%20%EB%A7%B5%20%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC.cpp