[백준 9466번] BFS(너비 우선 탐색) - 텀 프로젝트

✨ 문제 ✨

✨ 정답 ✨

const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim();


// const fs = require('fs'); 
// let input = fs.readFileSync("/dev/stdin").toString().trim();

input = input.split('\n')

const 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;
}

🧵 참고한 정답지 🧵

https://velog.io/@sanbondeveloper/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%97%B0%EC%8A%B5-%EB%B0%B1%EC%A4%80-9466-%ED%85%80-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8

💡💡 기억해야 할 점 💡💡

visited를 두 개 만드는 경우도 있구나....