백준 17090 미로 탈출하기

17090번: 미로 탈출하기

문제

1번 예제

1번 예제를 살펴보면 모든 영역에서 D이므로 아래로 내려가면서 경계선 밖으로 이탈합니다.

따라서 모두 미로 탈출이 가능하므로 정답은 9가 됩니다.

 

풀이.

시간을 단축하기 위해 DP 알고리즘과  DFS알고리즘을 적절히 사용해줍니다.

 

DFS알고리즘을 사용하여 탐색한 경우 이미 도달한 적이 있었던 칸은 이미 결과가 정해 져 있기 때문에 다시 한번 탐색할 필요가 없습니다.

 

1. dp 배열을 칸수만큼 만들어주고 기본값으로 -1을 할당해 주었습니다. -1의 경우 방문한 적이 없다는 것을 뜻합니다. 0의 경우 방문하였지만 탈출하지 못한 경우, 1의 경우 방문하였고, 탈출 가능했던 칸이라고 표시합니다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let N, M;
let input = [];
const dx = [0, 1, 0, -1];
const dy = [-1, 0, 1, 0]; // U R D L
const dir = { U: 0, R: 1, D: 2, L: 3 };
let dp = [];

function dfs(y, x) {
  // 방문한 적이 있으니, 기록되어 있던 결과값을 그대로 return
  if (dp[y][x] !== -1) return dp[y][x];
  dp[y][x] = 0; // 방문 표시 '0' 할당

  const nDir = dir[input[y][x]];
  const nx = x + dx[nDir];
  const ny = y + dy[nDir];

  // miro 경계선에서 벗어난 경우이므로 '1'을 할당하여 탈출 가능함을 기록
  if (nx < 0 || ny < 0 || nx >= M || ny >= N) {
    dp[y][x] = 1;
  } else {
    dp[y][x] = dfs(ny, nx);
  }
  return dp[y][x];
}

rl.on("line", function (line) {
  if (!N) {
    [N, M] = line.split(" ").map(Number);
    dp = Array.from({ length: N }, () => Array(M).fill(-1));
  } else {
    input.push(line.split(""));

    if (input.length === N) {
      let result = 0;

      for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
          const isPossible = dfs(i, j);
          result += isPossible ? 1 : 0;
        }
      }

      console.log(result);
      rl.close();
    }
  }
});