백준13565 - 침투 (DFS) node.js

https://www.acmicpc.net/problem/13565

 

해당 문제는 DFS 알고리즘에 대해 이해하고 있다면 쉽게 해결할 수 있다.

 

문제 풀이 과정

이 문제에서 유의할 점이 있다면 백준의 여타 다른 DFS 문제와 달리 모든 좌표에 DFS 알고리즘을 동작시키는 것이 아니다.

outer side인 첫 번째 배열에서만 값이 이동가능한 좌표인 경우(0인 경우) DFS 알고리즘을 동작시킨 뒤, 마지막 배열에 방문 기록이 존재하는지 파악 후 답안을 출력했다.

 

전체 소스 코드

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

function solution(data) {
  const [Y, X] = data.shift().split(" ").map(Number);
  const matrix = data.map((el) => el.split("").map(Number));
  const visited = Array.from({ length: Y }, () => {
    return Array.from({ length: X }, () => 0);
  });
  matrix[0].forEach((_, j) => {
    if (!matrix[0][j] && !visited[0][j]) DFS(visited, matrix, 0, j);
  });

  console.log(visited.at(-1).includes(1) ? "YES" : "NO");
}

function DFS(visited, matrix, y, x) {
  const queue = [[x, y]];
  let queueIdx = 0;
  visited[y][x] = 1;
  while (queue.length > queueIdx) {
    let [x, y] = queue[queueIdx++];
    const directions = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ];
    for (let i = 0; i < directions.length; i++) {
      const [dx, dy] = directions[i];
      const [nx, ny] = [dx + x, dy + y];
      if (
        verify(matrix[0].length, matrix.length, nx, ny) &&
        !visited[ny][nx] &&
        !matrix[ny][nx]
      ) {
        visited[ny][nx] = 1;
        queue.push([nx, ny]);
      }
    }
  }
}

function verify(X, Y, x, y) {
  return 0 <= x && x < X && 0 <= y && y < Y;
}

solution(input);