[Node.js] 16929. Two Dots

문제 설명

아래 그림과 같이 사이클을 찾는 문제이다.

그림 1, 2 모두 사이클이 있는 경우로 "Yes" 를 출력하고, 만약 존재하지 않다면 "No"를 출력한다.

 

문제 풀이

기본적으로는 dfs 코드를 차용했다.

 

하지만 방문했던 곳을 어떻게 또 방문을 할까?에 대해 생각했고, 내가 얻은 답은 다음과 같다.

 

✨ visited 배열 -> 시작 노드부터 현재 노드까지의 거리를 저장한 배열

 

첫번째 그림

사이클을 찾고자 한다면, 4 -> 1로 돌아가야한다.

현재 노드가 (r, c) 이고, 다음 노드가 (nr, nc) 일 때

visited[r][c] - visited[nr][nc] >= 3 일 때, 사이클이 발생한다. --- (1)

 

두번째 그림

시작노드를 포함해서는 사이클이 없지만, 이동하다보면 뒤에 사이클이 발견되는 경우이다.

이 경우도 (1) 의 로직을 적용한다면, 

6 -> 3으로 돌아가야하고, visited 배열 값의 차이가 3이상이므로, 사이클이 발생한다.

 

구체적인 dfs 코드이다.

 

정답 코드

const fs = require("fs");
const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const grid = input.slice(1);

const boolCycle = solution();
console.log(boolCycle ? "Yes" : "No");

function solution() {
  // 모든 칸을 순회하면서, 사이클이 있는지 검사
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (canBeCycle(i, j)) {
        return true;
      }
    }
  }

  if (canBeCycle(0, 0)) return true;
  return false;
}

function canBeCycle(startR, startC) {
  const dr = [0, 1, 0, -1];
  const dc = [1, 0, -1, 0];
  const visited = Array.from({ length: N }, () => Array(M).fill(0));

  function dfs(r, c) {
    for (let i = 0; i < 4; i++) {
      const nr = r + dr[i];
      const nc = c + dc[i];

      if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

      if (grid[nr][nc] === grid[r][c]) {
        // 방문한 적있고, 사이클을 이루는 경우
        if (visited[nr][nc] > 0) {
          if (visited[r][c] - visited[nr][nc] >= 3) {
            return true;
          }
        } else {
          visited[nr][nc] = visited[r][c] + 1;
          if (dfs(nr, nc)) return true;
        }
      }
    }
    return false;
  }

  visited[startR][startC] = 1;
  return dfs(startR, startC);
}

 

결과

 

문제 바로가기 링크

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