[백준] 16197번 두 동전 - JavaScript(NodeJS)

문제

16197번: 두 동전

 

풀이

문제의 조건을 요약해보자.

 

동전이 2개 주어진다.
버튼을 클릭해서 동전을 상하좌우로 이동시킨다.
동전은 벽을 넘을 수 없고, 보드에서 떨어뜨릴 수 있다.
두 동전은 같은 방향으로 한 칸씩 이동한다.

 

이를 참고해 두 동전 중 하나만을 떨어뜨리기 위해 버튼을 최소 몇번 눌러야 할지 구하자.

 

풀이 방향

우선 동전의 위치를 구해야 한다.

별 다른 방법이 없으므로, 보드 행렬에서 한칸씩 모두 조회해야 한다.

 

2개의 동전의 위치를 모두 구했다면, 버튼을 눌러 동전을 이동시킨다.

버튼은 최대 10번 누를 수 있다.

 

경우의 수는 상하좌우로 총 4번, 4의 10승 = 최대 약 100만번으로 조회해보기에 충분하다.

DFS를 통해 모든 경우의 수를 조회해본다.

 

재귀를 탈출하기 위한 조건을 설정한다.

 

1. 버튼을 10번 초과시켜서 눌렀다면 탈출
2. 두 동전이 모두 떨어지면 탈출
3. 두 동전중 한 동전이 떨어졌다면, 최솟값 여부를 판별하고 탈출

 

그리고 상하좌우 이동을 판별할 때, 벽이 있다면 이동할 수 없음을 반영한다.(벽에 걸리는 코인은 이동시키지 않으면 된다.)

 

최솟값 판단은 오로지 한개의 동전만 떨어졌을 때 실행되므로
dfs 재귀가 모두 끝나고 정답을 출력하기 전에

최솟값이 갱신되지 않았다면 10회 안에 하나의 동전만을 떨어뜨리는게 불가능하므로, -1을 출력한다.

갱신되었다면 최솟값을 출력하면 되겠다.

 

이제 코드를 보자.

 

코드

const sol = (input) => {
  const [N, M] = input[0].split(" ").map(Number);
  const board = input.slice(1).map((str) => str.split(""));
  const coin = [];
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (board[i][j] === "o") coin.push([i, j]);
    }
  }

  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];
  let min = Number.MAX_SAFE_INTEGER;

  function checkDrop(x, y) { // 떨어지면 참, 떨어지지 않았으면 거짓
    if (x < 0 || y < 0 || x >= N || y >= M) return true;
    return false;
  }

  function checkWall(x, y, idx) {
    const [nx, ny] = [x + dx[idx], y + dy[idx]];
    if (board[nx]) { 
      if (board[nx][ny] === "#") return [x, y];
    }
    return [nx, ny];
  } // 중요한 부분. 먼저 행이 존재하는지를 검사한다.(board[-1][2]는 undefined의 2번 인덱스를 참조하려 하기 때문에 에러가 발생한다.)

  function dfs(cnt, x1, y1, x2, y2) {
    if (cnt >= min) return; // 없어도 정답은 나온다. 하지만 10이하의 min값이 나왔다면 더 빠르게 돌아간다. 
    if (cnt > 10) return;
    if (checkDrop(x1, y1) && checkDrop(x2, y2)) return;
    if (checkDrop(x1, y1) || checkDrop(x2, y2)) { // 둘 중 하나만 참일 때만이 최솟값을 갱신할 수 있다.
      min = Math.min(min, cnt);
      return;
    }
    for (let i = 0; i < 4; i++) {
      const [nx1, ny1] = checkWall(x1, y1, i); // 벽이 있으면 (x,y), 벽이 없다면 이동 가능하므로 (nx,ny)
      const [nx2, ny2] = checkWall(x2, y2, i); // 단, (nx,ny)가 보드 바깥일 수도 있지만, 다음 재귀에서 판별할 것이기 때문에 상관x
      dfs(cnt + 1, nx1, ny1, nx2, ny2);
    }
  }

  dfs(0, coin[0][0], coin[0][1], coin[1][0], coin[1][1]);
  if (min === Number.MAX_SAFE_INTEGER) return -1; // 최솟값이 갱신되지 않았다면!
  return min;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });