[BOJ] 9466번 - 텀 프로젝트

🔥 접근

1. slice 를 이용해 각 테스트케이스를 나눈 후에 그래프를 만든다.
2. 간선이 한개 + 단방향으로 이루어진 그래프이므로 큐를 만들지 않고 visited 로만 방문을 했는지 판단 가능하다고 생각
3. 모든 정점을 한번씩은 다 방문해야하므로 for문으로 모든 정점을 돌되, 이미 방문했던 곳은 return
4. 그래프에서 한 싸이클을 찾기 위해서 path 배열을 두고, 마지막으로 방문한 정점에서 다음 노드가 path 에 있는지 indexOf 를 이용하여 판단
   • 이때 path 내부에 해당 노드가 존재한다면(-1이 아닐때) 해당 인덱스부터 path의 마지막 요소까지 한 싸이클이 완성 된 것!
   • -1 이라면 한 싸이클이 만들어지지 않았기때문에 count를 올리지 않음
5. 전체 학생 수 - count 를 하여 답을 도출

🧑‍💻 코드

const fs = require('fs');

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

const T = input.shift();

function solution() {
  for (let i = 0; i < T; i++) {
    const [n, nums] = input.slice(i * 2, i * 2 + 2);
    const total = Number(n);
    const students = [-1, ...nums.split(' ').map(Number)];

    console.log(bfs(total, students));
  }
}

function bfs(total, graph) {
  const visited = Array(total + 1).fill(false);
  let count = 0;

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

    let current = i;
    const path = [];

    while (!visited[current]) {
      visited[current] = true;
      path.push(current);
      current = graph[current];
    }

    const idx = path.indexOf(current);
    if (idx !== -1) {
      count += path.length - idx;
    }
  }

  return total - count;
}

solution();

 

🔗 관련 링크

• https://www.acmicpc.net/problem/9466