🔎 게임 맵 최단거리

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/1844

📄 제출 코드

//maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
function solution(maps) {
    var answer = 1;
    let visited = maps;
    let dx = [-1, 1, 0, 0];
    let dy = [0, 0, -1, 1];
    let n = maps.length;
    let m = maps[0].length;
    let q = [[0, 0]];
    visited[0][0] = 0;
    while (q.length != 0) {
        let size = q.length;
        for (let i = 0; i < size; i++) {
            let [x, y] = q.shift();
            for (let j = 0; j < 4; j++) {
                let nx = dx[j] + x;
                let ny = dy[j] + y;

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] == 0) continue;
                if (nx == n - 1 && ny == m - 1) return answer += 1;
                q.push([nx, ny]);
                visited[nx][ny] = 0;
            }
        }
        answer++;
    }
    return -1;
}
let maps = [[1, 0, 1, 1, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1]];
console.log(solution(maps));

간단한 bfs문제 였다.
4방탐색을 하면서 visited를 따로 true,false로 채우지 않고 그냥 map을 복사해서 지나간곳은 0으로 바꿔버렸다.

우선 시작점을 set한다.

 let q = [[0, 0]];
visited[0][0] = 0;

그리고 q가 빌때까지 반복을 하는데 이 때 문제에서 시작점은 좌측 상단, 도착점은 우측상단이라고 명시되있기 때문에 0,0으로 바로 시작한다.
(다른 bfs경우 map에서 시작점을 찾아서 거기서 bfs를 시작해줘야함.)

while (q.length != 0) {
  let size = q.length;
  for (let i = 0; i < size; i++) {
    let [x, y] = q.shift();
    for (let j = 0; j < 4; j++) {
      let nx = dx[j] + x;
      let ny = dy[j] + y;

      if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny] == 0) continue;
      if (nx == n - 1 && ny == m - 1) return answer += 1;
      q.push([nx, ny]);
      visited[nx][ny] = 0;
    }
  }
  answer++;
}

4방탐색을 하면서 범위 밖인경우 continue를 해준다.
그리고 도착점(n-1,m-1)인 경우, 도착 했을 때까지 생각해서 +1하여 결과를 도출한다.
도착하지 않은 경우 q에 다시 변경위치를 push하고, 방문처리함.