[콭] 게임 맵 최단거리 BFS

코딩테스트 연습
깊이/너비 우선 탐색(DFS/BFS)
게임 맵 최단거리

로직

최단거리를 구해야 하므로 BFS 적용
1. (0,0)에서 시작해서 주변에서 데이터가 1인 좌표를 찾는다.
2. 지난 좌표의 데이터는 0으로 바꾸고 그 좌표로 나아간다.
3. 나아간 좌표가 맵을 벗어난거나 데이터가 0이면 돌아간다.

javascript 코드

function solution(maps) {
  let needVisit = [[0, 0, 1]];
  const row = maps.length - 1;
  const col = maps[0].length - 1;
  while (needVisit.length) {
    let [curX, curY, move] = needVisit.shift();

    if (curX === col && curY === row) return move;
    if (curX < 0 || curX > col || curY < 0 || curY > row) continue;
    if (maps[curY][curX] === 0) continue;
    if (maps[curY][curX]) {
      maps[curY][curX] = 0;
      needVisit.push([curX + 1, curY, move + 1]);
      needVisit.push([curX - 1, curY, move + 1]);
      needVisit.push([curX, curY + 1, move + 1]);
      needVisit.push([curX, curY - 1, move + 1]);
    }
  }
  return -1;
}

주의

! 조건을 잘 확인하자

• row와 col이 다를 수도 있다는 걸 몰라서 헤맸음

! undefined가 뜬다면 변수 어딘가 잘못 된거임

• type이 틀리거나 앞에서 탈출이 안 된 것일 수 있음

23.04.03 다시 풀기

BFS라고 생각하고 당연히 모든 좌표를 확인하는 이중for문부터 돌렸는데
이 문제는 시작 좌표가 정해져있으므로 [0,0]을 방문해야할 노드에 넣어두고 방문할 노드가 없어질 때까지만 반복하면 된다.
"당연히 --다" 이런 생각을 전향할 필요가 있겠다.

function solution(maps) {
  let n = maps.length;
  let m = maps[0].length;
  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];
  let visit = [];

  function BFS() {
    visit.push([0, 0, 1]);
    while (visit.length) {
      let [curX, curY, move] = visit.shift();
      for (let k = 0; k < 4; k++) {
        let [moveX, moveY] = [curX + dx[k], curY + dy[k]];
        if (moveX === n - 1 && moveY === m - 1) return move + 1;
        if (moveX < 0 || moveX >= n || moveY < 0 || moveY >= m) continue;
        if (!maps[moveX][moveY]) continue;

        maps[moveX][moveY] = 0;
        visit.push([moveX, moveY, move + 1]);
      }
    }
    return -1;
  }

  return BFS();
}

console.log(
  solution([
    [1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 1, 1],
    [1, 1, 1, 0, 0],
    [0, 0, 0, 1, 1],
  ])
);