[프로그래머스][bfs] 미로 탈출 명령어

     

목차

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

 

 

문제 구현 방향

가지치기를 잘하면 되는 문제이다. 또한 사전순 탐색이기 때문에 bfs에서 break구문을 걸어주면 된다.

 

 

코드 구현

let dir = [
  [1, 0, "d"],   
  [0, -1, "l"],  
  [0, 1, "r"],   
  [-1, 0, "u"],  
];

function solution(n, m, x, y, r, c, k) {
  x -= 1;
  y -= 1;
  r -= 1;
  c -= 1;

  let minDist = Math.abs(r - x) + Math.abs(c - y);
  //최소거리가 더 크므로 불가능
  if (minDist > k) return "impossible";
  
  // 반환값이 없으므로 불가능
  return bfs(n, m, x, y, r, c, k) || "impossible";
}

function bfs(n, m, x, y, r, c, k) {
  let queue = [];
  queue.push([x, y, 0, ""]);

  while (queue.length) {
    let [cx, cy, cnt, path] = queue.shift();

    if (cnt === k && cx === r && cy === c) {
      return path;
    }

    for (let i = 0; i < 4; i++) {
      let nx = cx + dir[i][0];
      let ny = cy + dir[i][1];

      if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
	  //남은 거리가 최소거리보다 크므로 불가능
      let rest = Math.abs(r - nx) + Math.abs(c - ny);
      if (cnt + 1 + rest > k) continue;

      queue.push([nx, ny, cnt + 1, path + dir[i][2]]);
      //사전 순 탐색이므로 바로 중단
      break; 
    }
  }
}