백준 16197 두 동전

문제

제한 사항

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const sol = (input) => {
  const [row, column] = input.shift().split(" ").map(Number);
  const graph = input.map((e) => e.split(""));

  // 방향 이동용 배열
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  // 동전의 좌표를 저장할 배열
  const coinCoordinate = [];
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < column; j++) {
      if (graph[i][j] === "o") {
        // 동전의 첫 좌표가 저장
        coinCoordinate.push([i, j]);
      }
    }
  }

  // graph 바깥으로 떨어지는 지 확인
  const checkDrop = (x, y) => {
    if (x < 0 || y < 0 || x >= row || y >= column) return true;
    return false;
  };

  // 벽인지 확인
  const checkWall = (x, y, index) => {
    const [nx, ny] = [x + dx[index], y + dy[index]];
    // 행을 먼저 확인해야 함.
    if (graph[nx]) {
      // 어우 제자리 걸음
      if (graph[nx][ny] === "#") return [x, y];
    }
    return [nx, ny];
  };

  let min = Number.MAX_SAFE_INTEGER;
  const dfs = (cnt, x1, y1, x2, y2) => {
    if (cnt >= min) return;
    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);
      const [nx2, ny2] = checkWall(x2, y2, i);
      dfs(cnt + 1, nx1, ny1, nx2, ny2);
    }
  };

  dfs(
    0,
    coinCoordinate[0][0],
    coinCoordinate[0][1],
    coinCoordinate[1][0],
    coinCoordinate[1][1]
  );

  return min === Number.MAX_SAFE_INTEGER ? -1 : min;
};

console.log(sol(input));

복습

const sol = (n, m, graph) => {
  // 방향 이동용 배열
  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  // coin 위치 저장
  const coin = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (graph[i][j] === "o") {
        coin.push([i, j]);
      }
    }
  }

  // graph 바깥으로 떨어지는 check
  const checkDrop = (x, y) => {
    if (x < 0 || y < 0 || x >= n || y >= n) return true;
    else return false;
  };

  // 다음 이동 칸이 벽이라면 움직이지 않음, 제자리 걸음
  const checkWall = (x, y, index) => {
    const [nx, ny] = [x + dx[index], y + dy[index]];

    if (graph[nx][ny]) {
      if (graph[nx][ny] === "#") return [x, y];
    }
    return [nx, ny];
  };

  let min = Number.MAX_SAFE_INTEGER;
  // 동전 두개가 동시에 움직이는 dfs함수
  const dfs = (cnt, x1, y1, x2, y2) => {
    if (cnt > 10) return;

    if (checkDrop(x1, y1) && checkDrop(x2, y2)) return;

    if (checkDrop(x1, y1) || checkDrop(x2, y2)) {
      min = Math.min(min, cnt);
    }

    for (let i = 0; i < 4; i++) {
      const [nx1, ny1] = checkWall(x1, y1, i);
      const [nx2, ny2] = checkWall(x2, y2, i);

      dfs(cnt + 1, nx1, ny1, nx2, ny2);
    }
  };

  dfs(0, coin[0][0], coin[0][1], coin[1][0], coin[1][1]);

  return min === Number.MAX_SAFE_INTEGER ? -1 : min;
};