[백준] 9466번 텀프로젝트

9466번 텀프로젝트

1. 이해하기

• 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 문제이다.
• DFS를 이용해서 구한다.

---

2. 구현하기

• dfs(here,arr,visited,done)

  • 현재 학생을 가리키는 here 와 이미 체크한 학생인지를 나타내는 visited 프로젝트 팀원에 속하는지 여부까지 확인하는 done을 가진다.
  • 다음번 학생을 비교하는데 체크하지 않았으면 dfs를 다시 하고, 체크를 한 상태에서 아직 프로젝트 팀원 여부를 확인하지 않았다면 이에 해당하는 학생수를 세준다. 이 때 하는 작업이 순환이 생기는 곳을 찾아서 그 때의 원소 수를 세주는 것이다.

  static void dfs(int here, int[] arr, boolean[] visited, boolean[] done) {
          visited[here] = true;
  
          int there = arr[here];
          if(!visited[there]) {
              dfs(there,arr,visited,done);
          } else if(!done[there]){
              for(int i = there; i != here; i = arr[i]) {
                  cnt++;
              }
              cnt++;
          }
  
          done[here] = true;
      }

---

3. 전체 코드

import java.util.Scanner;

public class Main {
    static int cnt = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc = 1; tc <= T; tc++) {
            cnt = 0;
            int N = sc.nextInt();
            int[] arr = new int[N+1];
            boolean[] visited = new boolean[N+1];
            boolean[] done = new boolean[N+1];
            for(int i = 1; i <= N; i++)
                arr[i] = sc.nextInt();

            for(int i = 1; i <= N; i++) {
                if(done[i]) continue;
                dfs(i,arr,visited,done);
            }

            System.out.println(N-cnt);
        }
    }

    static void dfs(int here, int[] arr, boolean[] visited, boolean[] done) {
        visited[here] = true;

        int there = arr[here];
        if(!visited[there]) {
            dfs(there,arr,visited,done);
        } else if(!done[there]){
            for(int i = there; i != here; i = arr[i]) {
                cnt++;
            }
            cnt++;
        }

        done[here] = true;
    }
}

---

4. 배운 점

• 배열의 사이클이 형성되었을 때 어떤 식으로 찾는지에 대해 배웠다.
• 굳이 하나의 배열로 판단하려고 하지 않고 다른 배열을 하나 더 생성하여 확인을 하면 된다는 것 또한 배웠다.