문제 개요

문제: 두 동전

분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

난이도: 골드4

문제 풀이

DFS로 풀이했다.

이동 횟수를 계속해서 증가시키며 상하좌우 4방향으로 동전을 이동시킨다. 더이상 탐색할 필요가 없는 아래의 두 경우에는 곧바로 함수를 종료하여 불필요한 실행을 막는다.

• 이동 횟수가 현재 정답보다 같거나 커지는 경우
• 이동 횟수가 10을 넘어가는 경우

이동시킨 동전의 범위를 검사하여 둘 중 하나만 떨어졌을 때 정답을 갱신한다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [NM, ...board] = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = NM.split(" ").map(Number);
board = board.map((row) => row.split(""));

const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
let answer = Infinity;

const checkRange = (y, x) => {
  if (y < 0 || y >= N || x < 0 || x >= M) return false;
  return true;
};

const checkWall = (y, x) => {
  return checkRange(y, x) && board[y][x] === "#" ? true : false;
};

const dfs = (moveCnt, y1, x1, y2, x2) => {
  // 더이상 탐색할 필요가 없는 경우 곧바로 함수를 종료하여 불필요한 실행을 막는다.
  if (answer <= moveCnt) return;
  if (moveCnt > 10) return;

  // 떨어진 동전의 개수를 구한다.
  let fallCnt = 0;
  if (!checkRange(y1, x1)) fallCnt++;
  if (!checkRange(y2, x2)) fallCnt++;

  // 하나만 떨어졌을 경우에 정답을 갱신한다.
  if (fallCnt > 0) {
    if (fallCnt === 2) return;
    answer = Math.min(answer, moveCnt);
    return;
  }

  // 동전을 이동시킨다.
  for (let i = 0; i < 4; i++) {
    let ny1 = y1 + dy[i];
    let nx1 = x1 + dx[i];
    let ny2 = y2 + dy[i];
    let nx2 = x2 + dx[i];

    if (checkWall(ny1, nx1) && checkWall(ny2, nx2)) continue;
    else if (checkWall(ny1, nx1)) dfs(moveCnt + 1, y1, x1, ny2, nx2);
    else if (checkWall(ny2, nx2)) dfs(moveCnt + 1, ny1, nx1, y2, x2);
    else dfs(moveCnt + 1, ny1, nx1, ny2, nx2);
  }
};

const solution = () => {
  let coin = [];

  board.forEach((row, rowIdx) =>
    row.forEach((item, colIdx) => {
      if (item === "o") coin.push([rowIdx, colIdx]);
    })
  );

  dfs(0, coin[0][0], coin[0][1], coin[1][0], coin[1][1]);
  console.log(answer === Infinity ? -1 : answer);
};

solution();