백준 9466 텀 프로젝트

문제

팀원 수에 제한이 없는 텀 프로젝트에서 함께하고 싶은 학생을 골라야 한다. 각각 한 명씩 고를 수 있다. 이 때 팀이 생성되는 경우는 서로 선택했던 한 사람을 계속 거치고 거쳐 다시 처음 학생으로 돌아오는 사이클이 형성되어야만 팀이 될 수 있다. 즉 사이클이 다시 돌아오지 않으면 팀 구성은 실패한 사람이 되는 것이다. 사이클은 계속 서로가 향하는 팀원을 향해 가야 하기 때문에 dfs로 알고리즘을 짜야했다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
for (let i = 1; i < inputs.length - 1; i += 2) {
  const n = +inputs[i];
  const students = [0, ...inputs[i + 1].split(" ").map(Number)];
  const visited = new Array(n + 1).fill(false);
  const finished = new Array(n + 1).fill(false);
  let group = 0;
 
  function dfs(node) {
    visited[node] = true;
    let next = students[node];
 
    if (!visited[next]) {
      dfs(next);
    } else if (!finished[next]) {
      let count = 1;
      let cur = next;
      while (cur !== node) {
        count++;
        cur = students[cur];
      }
      group += count;
    }
 
    finished[node] = true;
  }
 
  for (let j = 1; j <= n; j++) {
    if (!visited[j]) dfs(j);
  }
 
  console.log(n - group);
}
 

모든 학생들을 한번씩 돌되, 각각 dfs를 돌도록 해주었다. 기존 방문한 학생들만 기록하게 된다면, 결국 나중에는 이전에 갔지만 그룹이 성사되지 못한 곳 또한 방문 처리가 되어있기 때문에 이 정보만으로는 부족했다. 따라서 finished라는 배열을 따로 두었다.

dfs에서는 해당 인덱스에 있는 값, 즉 해당 학생이 가리키는 학생을 가리키도록 했고, 만약 방문하지 않은 노드가 있다면 dfs를 다음으로 돌렸다. 왜 이렇게 굳이 따로 처리를 해줘야 하냐면 방문하지 않은 노드의 경우 계속 dfs가 호출되어 한바퀴를 돌게 된다. 이렇게 돌면서 방문 처리는 되었지만 아직 finished에 처리는 되지 않은 상태이다.

그렇게 되면 한바퀴를 돌고 다시 돌아와서 다시 조건문으로 가면 다음 else if문으로 가게 된다. 그렇게 되면 다시금 dfs로 돌면서 현재 있는 그룹의 명수만큼을 세서 group에 추가할 수 있게 된다. 그렇게 사이클이 완성된 그룹은 모두 finished처리가 될 것이다.

이런 식으로 모든 노드들에 대해서 검색을 할 수 있도록 하면 루프가 끝날 때, 모든 노드들에 방문 처리는 되어있지만 제대로 만들어지지 않은 그룹에 대해서는 finished가 체크되어있지 않아 그룹이 만들어진 사람과 아닌 사람을 구별할 수 있게 된다.