[백준] 9466 텀 프로젝트

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

2020-12-01

---

import java.util.Scanner;
 
public class Main9466 {
    public static int answer, N, arr[];
    public static boolean vtd[], check[];
 
    public static void solve(int num) {
        vtd[num] = true;
        int next = arr[num]; // next value
        if(!vtd[next]) { // never visited
            solve(next);
        } else if (!check[next]) { // visited && not chekced?
            for(int i = next; i != num; i = arr[i]) {
                answer++;
            }
            answer++;
        }
        check[num] = true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
 
        for(int ts = 1; ts <= test; ts++) {
            N = sc.nextInt();
            arr = new int[N+1];
            vtd = new boolean[N+1];
            check = new boolean[N+1];
            answer = 0;
 
            for(int i = 1; i <= N; i++) {
                int x = sc.nextInt();
                arr[i] = x;
            }
 
            for(int i = 1; i <= N; i++) {
                if(!vtd[i]) solve(i);
            }
            System.out.println(N-answer);
        }
    }
}

# 문제 요약

- 팀원 수에는 제한이 없다 (S1 -> S1 도 가능)

- 2 <= N <= 100,000

- S1 -> S2 -> S3 -> .... -> Sr -> S1 인 경우에만 팀으로 인정된다.

 

학생	1	2	3	4	5	6	7
선택	3	1	3	7	3	4	6

위와 같은 경우 (S3 -> S3) , (S4 -> S7 -> S6 -> S4) 두 경우를 제외하고는 팀을 만들 수 없다. 

 

 

# 풀이

1. 입력

 

arr = new int[N + 1];
vtd = new boolean[N + 1];
check = new boolean[N + 1];

arr라는 int 배열은 각 학생별로 같이 프로젝트 하고 싶은 학생이 누구인지 정하게 된다.

vtd라는 boolean 배열은 방문한지 아닌지를 체크하게 된다.

check라는 boolean 배열은 다시 방문할 필요가 있는지 없는지를 체크하게 된다.

 

for(int i = 1; i <= N; i++) {
      int x = sc.nextInt();
      arr[i] = x;
}
 
for(int i = 1; i <= N; i++) {
      if(!vtd[i]) solve(i);
}

 

마지막에 전체 N에서 answer만큼 빼주면, 팀을 만들지 못한 학생의 수를 구할 수 있다.

 

 

 

+) 계속 답이 이상하게 안 맞아서 결국 마지막에는 힌트를 얻었다. 결국 다른 사람들의 풀이를 찾아봤는데, 아무리 봐도 다른 블로그 풀이와 거의 유사했다. 아예 대놓고 코드 하나하나 비교해봤더니, 마지막 check하는 부분때문에 계속 틀린거였었다..