백준 2668 숫자고르기

2668번: 숫자고르기

예제

간단히 예제를 살펴보면 싸이클이 발생한 구간 1, 3, 5를 순서대로 출력하면 됩니다.

즉. 무한 싸이클이 발생하는 구간의 정수들을 모두 순서대로 출력해주면 됩니다.

 

1. 깊이 우선 탐색(DFS) 알고리즘을 이용해 싸이클이 발생하는지 확인합니다.

 

2. 싸이클이 발생하였다면, 그 때 방문했던 모든 노드들은 정답이 되기때문에 'check'배열에 따로 저장해주겠습니다.

 

3. 위와 같이 N개의 노드를 탐색하면 되는데, 이전에 싸이클이 발생했던 구간(check[n] === true)의 경우 이미 자신을 제외한 다른 싸이클에 속해있다는 의미로 다시 방문해 줄 필요가 없습니다. 따라서 바로 return false; 해주었습니다.

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let N;
let input = [0];
let visit = [];
let check = []; // 싸이클에 속한 노드들 체크하는 배열

function dfs(node, target) {
  if (check[node]) return false;
  if (!visit[node]) {
    visit[node] = true;
    return dfs(input[node], target);
  }

  if (node === target) {
    return true;
  }

  return false;
}

rl.on("line", function (line) {
  if (!N) {
    N = +line;
    check = Array.from({ length: N + 1 }, () => false);
  } else {
    input.push(+line);

    if (input.length === N + 1) {
      let result = [];
      for (let i = 1; i <= N; i++) {
        visit = Array.from({ length: N + 1 }, () => false);
        const isCycle = dfs(i, i);

        if (isCycle) {
          for (let j = 1; j <= N; j++) {
            if (visit[j]) {
              check[j] = true;
            }
          }
        }
      }

      for (let i = 1; i < check.length; i++) {
        if (check[i]) result.push(i);
      }
      result.unshift(result.length);
      console.log(result.join("\n"));
      rl.close();
    }
  }
});