탈주범 검거

문제 설명

문제 링크

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : path.join(__dirname, "input.txt"))
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 0;
  const T = Number(input[idx++]);
  const tunnel = {
    0: [],
    1: [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ], // 상하좌우
    2: [
      [-1, 0],
      [1, 0],
    ], // 상하
    3: [
      [0, -1],
      [0, 1],
    ], // 좌우
    4: [
      [-1, 0],
      [0, 1],
    ], // 상우
    5: [
      [1, 0],
      [0, 1],
    ], // 하우
    6: [
      [1, 0],
      [0, -1],
    ], // 하좌
    7: [
      [-1, 0],
      [0, -1],
    ], // 상좌
  };

  for (let tc = 0; tc < T; tc++) {
    const [N, M, R, C, L] = input[idx++].split(" ").map(Number);

    const arr = [];
    for (let i = 0; i < N; i++) {
      arr.push(input[idx++].split(" ").map(Number));
    }

    const bfs = (r, c) => {
      const visited = Array.from({ length: N }, () => Array(M).fill(0));
      visited[r][c] = 1;

      const queue = [[r, c]];
      let head = 0;
      let cnt = 1;

      while (queue.length > head) {
        const [x, y] = queue[head++];

        if (visited[x][y] >= L) continue;

        for (let [dx, dy] of tunnel[arr[x][y]]) {
          const nr = x + dx;
          const nc = y + dy;

          if (0 <= nr && nr < N && 0 <= nc && nc < M) {
            if (!visited[nr][nc] && arr[nr][nc] !== 0) {
              const canConnect = tunnel[arr[nr][nc]].some(([nx, ny]) => nx === -dx && ny === -dy);

              if (canConnect) {
                visited[nr][nc] = visited[x][y] + 1;
                queue.push([nr, nc]);
                cnt += 1;
              }
            }
          }
        }
      }

      return cnt;
    };

    let cnt = bfs(R, C);
    console.log(cnt);
  }
};

solution(input);

아이디어

1. 이동할 수 있는 터널의 좌표 정의
2. 배열에서 터널에 속하는 좌표의 점들을 뽑아서 bfs 진행
3. 다음에 갈 수 있는 터널의 좌표 안에 현재 좌표의 반대 좌표가 들어있는 지 확인한 뒤 bfs 탐색 이어서 하기
4. 결과값 도출

후기

이거는 과거 싸피에서 풀었던 탈주범 검거를 다시 한 번 풀어보자는 얘기를 들어서 다시 한번 풀어봤는데 문제 자체는 쉬웠다. 어떤 경우에 터널이 연결되어 있는 지 생각하면 쉽게 풀리는 문제였던듯? 근데 좌표값 정의할 때 생각보다 틀릴 수 있어서 다시 검사 해보고 할 것. 근데 예산ㄹ에 풀 때는 뭔가 이해도 어려웠던 것 같고 오래 걸렸던 것 같은데 금방 푼 거보니까 조금이라도 늘긴 늘었다..!