## 🌟 문제
[코딩테스트 연습 - 게임 맵 최단거리 \| 프로그래머스 스쿨](https://school.programmers.co.kr/learn/courses/30/lessons/1844)
N X M 크기의 게임 맵에서 `(0, 0)` 위치에서 출발해서 상대 진영 `(N - 1, M - 1)` 까지 도달하는 최단 경로의 칸 개수를 구하는 문제. 벽(0)으로는 지나갈 수 없고, 통로(1)로만 이동 가능하다.
## 🌟 풀이
최단 경로를 찾는 전형적인 BFS 문제이다.
- 시작점에서 가까운 곳부터 순서대로 탐색하기 때문에 처음 상대 진영에 도달했을 때의 거리가 최단경로이다.
- DFS는 비슷하지만 모든 경로를 탐색해야 하기 때문에(상대 진영에 도달한 이후에도 계속 탐색해야 함) 비효율적이다.
**DFS 구현 포인트**
1. shift는 O(N)시간복잡도를 갖기 때문에 frontIdx를 활용해서 O(1)로 동작하는 dequeue를 구현했다.
2. 시작점을 큐에 넣을 때 방문 처리를 잊지 말자.
3. 가중치가 없으므로 처음으로 상대 진영에 도착했을때의 경로 길이가 최단 경로이다. 그래서 따로 Math.min으로 최소 경로 길이를 비교할 필요 없다.
```javascript
function solution(maps) {
const queue = [];
let frontIdx = 0;
const rows = maps.length;
const cols = maps[0].length;
const visited = Array.from({ length: rows }, () =>
new Array(cols).fill(false)
);
const dx = [1, 0, -1, 0];
const dy = [0, 1, 0, -1];
const dequeue = () => {
const ret = queue[frontIdx];
frontIdx++;
return ret;
};
const goal = { x: cols - 1, y: rows - 1 };
const player = { x: 0, y: 0, length: 1 };
queue.push({ ...player });
visited[0][0] = true;
while (frontIdx < queue.length) {
const front = dequeue();
// 상대 진영 도착 확인
if (front.x === goal.x && front.y === goal.y) {
return front.length;
}
for (let di = 0; di < 4; di++) {
const nx = front.x + dx[di];
const ny = front.y + dy[di];
const nl = front.length + 1;
if (
nx < 0 ||
nx >= cols ||
ny < 0 ||
ny >= rows || // 범위 확인
maps[ny][nx] === 0 || // 길 확인
visited[ny][nx] // 방문 확인
) {
continue;
}
visited[ny][nx] = true;
queue.push({ x: nx, y: ny, length: nl });
}
}
return -1;
}
```