[백준] 16929번 Two Dots - JavaScript(NodeJS)

문제

16929번: Two Dots

 

풀이

N x M 크기의 게임판에서 사이클을 발견하는 문제이다.

 

문제에서의 사이클은 아래의 그림과 같이 4개 이상의 점들을 연결했을 때, 선이 아닌 도형을 이루면 된다.

위 그림에선 빨간 사이클과 주황 사이클이 존재한다.

 

풀이의 흐름은 다음과 같다.

 

dfs를 이용해보자.

 

1. 현재 위치로부터 동서남북 위치에 있는 노드로 이동이 가능한지를 판단한다.
2. 이동하려는 노드가 처음 출발한 노드와 색이 동일한지 판단한다.
3. 이동하려는 노드가 이미 방문한 곳인지 판단한다.
      방문하지 않았다면? => 방문한다.
      이미 방문했다면? => 이동한 노드 수가 4개 이상이어야 하며 이동하려는 노드가 처음 시작 노드와 같은지 판단한다.
            두 조건을 모두 만족한다면, 사이클이므로 재귀를 탈출하고 실행을 종료한다.

 

코드 흐름을 바탕으로 생각해보면,

위의 그림과 같은 게임판에서는, (0,0) 위치에서 출발하면 재귀를 탈출할 수 없다.
(0,1) 위치에서 출발해야 탈출 조건에 의해 재귀를 탈출할 수 있다.

 

그러므로 노드 시작점을 (0,0) ~ (N-1, M-1) 위치까지 모두 순회해 볼 것.

 

 

※ 일반적인 dfs에서는 종료 조건을 맨 앞에 넣는 경우가 많다.

하지만 이 문제는 이미 방문한 노드에 대해서도 조사를 해야 하기 때문에

이동할 노드의 방문 여부를 조회할 때 탈출 조건을 넣어주는 편이 편했다.

 

코드는 다음과 같다.

코드

const sol = (input) => {
  const [N, M] = input[0].split(" ").map(Number);
  const gameBoard = [];
  for (let i = 1; i <= N; i++) gameBoard.push(input[i].split("")); // N x M 게임판

  const check = Array.from({ length: N }, () => Array(M).fill(0)); // 방문 여부를 조회할 배열
  const dx = [-1, 0, 1, 0]; // 동서남북 좌표 이동
  const dy = [0, 1, 0, -1];
  let flag = 0; // 재귀 탈출을 위한 플래그

  function dfs(x, y, cnt) {
    if (flag) return;

    for (let i = 0; i < 4; i++) {
      const [nx, ny] = [x + dx[i], y + dy[i]];
      if (nx <= -1 || ny <= -1 || nx >= N || ny >= M) continue; // 게임판의 인덱스가 아니라면 패스
      if (gameBoard[nx][ny] !== gameBoard[start.x][start.y]) continue; // 시작한 색과 다르다면 패스
      if (!check[nx][ny]) { // 방문하지 않았다면 방문하고, 재귀가 끝나면 방문을 해제해 줘야 함.
        check[nx][ny] = 1;
        dfs(nx, ny, cnt + 1);
        check[nx][ny] = 0;
        continue;
      } else if (cnt >= 4 && nx === start.x && ny === start.y) {
        flag = 1; // 방문한 노드가 4개 이상, 이동하려는 좌표가 시작한 좌표라면 사이클이므로 재귀 탈출
        return;
      }
    }
  }

  let start;
  for (let x = 0; x < N; x++) {
    for (let y = 0; y < M; y++) {
      start = { x, y };
      check[x][y] = 1; // (0,0) ~ (N-1,M-1)까지 조회해야 하므로 방문했다면 방문을 해제해줘야 한다.
      dfs(x, y, 1);
      check[x][y] = 0;
      if (flag) break; // 사이클을 발견했다면 탈출한다.
    }
  }
  return flag ? "Yes" : "No"; // 사이클을 발견했으면 Yes 리턴, 사이클이 없다면 No 리턴
};

// 백준에서 입력을 받기 위한 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });