[알고리즘 연습] 백준 9466 (텀 프로젝트, 자바스크립트)

문제

백준 9466 텀 프로젝트

풀이

1) 방문하지 않은 노드부터 시작해 DFS를 수행하며 싸이클(같은 노드를 2번 방문한 경우)를 찾는다. 이 때 시간 초과를 방지하기 위해 모든 노드에 DFS를 1번 만 수행한다.

2) 싸이클로 인해 방문한 노드를 한 번 더 방문할 가능성이 있기 때문에 visited 외의 done이라는 배열이 추가적으로 필요하다. done까지 true일 경우 해당 노드는 다시는 방문할 필요가 없다.

3) 하나의 노드에 2번 방문한 경우 해당 노드의 사이클에 포함된 노드의 개수를 구한다. 이를 통해 팀에 속한 학생들의 수를 구할 수 있다.

소스 코드

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

let T = +input[0];
let index = 1;
let visited;
let done;
let arr;
let cnt = 0;

while (T > 0) {
  const n = +input[index];
  const temp = input[index + 1].split(" ").map((el) => +el);
  arr = [0, ...temp];
  visited = Array(n + 1).fill(false);
  done = Array(n + 1).fill(false);

  for (let i = 1; i <= n; i++) {
    if (visited[i]) continue;

    dfs(i);
  }

  console.log(n - cnt);

  index += 2;
  T -= 1;
  cnt = 0;
}

function dfs(node) {
  visited[node] = true;
  const next = arr[node];

  if (!visited[next]) dfs(next);
  else if (!done[next]) {
    for (let i = next; i !== node; i = arr[i]) {
      cnt += 1;
    }

    cnt += 1;
  }

  done[node] = true;
}