백준 13565 < 침투 > JavaScript

📍문제 링크

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

13565번: 침투

 

📍알고리즘 분류

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 깊이 우선 탐색

 

📍문제 풀이

높이 m, 너비 n 의 사각형이 주어질 때, 1번째 row의 0이 마지막 row의 0까지 연결되어 있는지를 확인

 

DFS를 통해 연결된 경로가 있으면 바로 YES를 출력하면 된다

 

📍코드 (JavaScript)

const [in1, ...map] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [row, column] = in1.split(" ").map(Number);

const dfs = () => {
  const isVisited = Array.from({ length: row }, (r) =>
    Array.from({ length: column }, (c) => false),
  );
  const stack = [];
  for (let i = 0; i < column; i++) {
    if (map[0][i] === "0") {
      stack.push([0, i]);
      isVisited[0][i] = true;
    }
  }
  if (!stack.length) return "NO";

  while (stack.length) {
    const [y, x] = stack.pop();
    if (y === row - 1) return "YES";

    // 상 (DFS니까 시행해야 할 듯)
    if (y - 1 >= 0 && !isVisited[y - 1][x] && map[y - 1][x] === "0") {
      stack.push([y - 1, x]);
      isVisited[y - 1][x] = true;
    }
    // 하
    if (y + 1 < row && !isVisited[y + 1][x] && map[y + 1][x] === "0") {
      stack.push([y + 1, x]);
      isVisited[y + 1][x] = true;
    }
    // 좌
    if (x - 1 >= 0 && !isVisited[y][x - 1] && map[y][x - 1] === "0") {
      stack.push([y, x - 1]);
      isVisited[y][x - 1] = true;
    }
    // 우
    if (x + 1 < column && !isVisited[y][x + 1] && map[y][x + 1] === "0") {
      stack.push([y, x + 1]);
      isVisited[y][x + 1] = true;
    }
  }
  return "NO";
};

console.log(dfs());

 

📍리뷰

- BFS였다면 윗 행이 모두 방문되었을 것이므로 체크하지 않아도 될 것 같다

- 하지만, DFS가 더 빠를 것 같아서 DFS를 실행

- BFS는 pop 대신 shift를 사용하고, 모든 depth를 방문해야 다음 depth로 넘어가기 때문에 DFS에 비해 느릴것임