백준 9466번 : 텀 프로젝트 (JAVA) 문제 풀이

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

9466번: 텀 프로젝트

---

 

✏️ 문제

 

🔐 문제 해결

이 문제는 생각보다 간단한데 어렵다.

위 예제 중 하나를  그림으로 표현해보았다.

그림이 좀 정신없긴 한데..

그림을 보면, (1번, 5번) -> 3번 과 팀을 이루고 싶어한다. 하지만 3번은 혼자 팀을 하길 원한다.

이렇게 되면 1번 5번은 팀을 이룰 수 없게 된다.

또, 2번-> 1번 -> 3번(혼자 팀) 이므로 2번도 팀을 이룰 수 없게 된다.

4번, 6번, 7번은 서로를 가리키고 있으므로 팀이 완성이 된다!

 

대충 어느정도 이해한 바탕으로 조건을 설정하면 아래와 같다.

1. 혼자 팀을 하고 싶어하는 사람을 선택한 사람은 팀을 이룰 수 없다.
2. 팀을 이루기 위해서는 서로를 선택해야만 한다. (위 그림 4, 6, 7번과 같이)

 

먼저 이 문제에서는 방문 여부 배열과, 팀 완성 여부 배열 이렇게 2가지 배열이 필요하다.

왜냐하면, 방문여부만 체크한다면 이 학생이 팀에 속해있는지 안 속해있는지 알 수 없기 때문이다.

boolean[][] visit, done;	// 방문 여부, 팀 완성 여부

 

1번 조건은, 입력을 받을 때 인덱스와 가리키는 학생의 인덱스가 같은 경우 팀 완성 배열에 체크를 해준다. (코드 일부분)

for(int i = 1; i <= N; i++){
    arr[i] = Integer.parserInt(st.nextToken());	// 위에서 StringTokenizer를 입력 받은 코드는 생략..
    
    if(arr[i] == i){
    	done[i] = true;	// 자기 자신을 가리키고 있으면 -> 팀 완성 체크!
        count++;	// 팀이 완성된 학생 수 증가
    }
}

 

2번 조건은, 자신이 가리키는 학생이 팀을 이룬적이 없고, 이미 방문했다는 건 -> 위 그림 4, 6, 7번 학생의 케이스이므로 팀이 완성이 된 것이다.

for(int i = 1; i <= N; i++) {
    if(!done[i]) {
    	dfs(i);
    }
}

-----------------------------

public static void dfs(int n){
    // 이미 방문 했을 때!
    if(visit[n]){
        done[n] = true;    // 팀 편성 완료했다고 처리
        count++;    // 팀 편성 완료 인원 증가
    }else{
        // 방문하지 않았을 때 -> 방문 처리!
        visit[n] = true;
    }
    
    // 다음 학생이 팀 결성을 아직 못했을 경우
    if(!done[arr[n]]){
        dfs(arr[n]);
    }
    
    // 해당 학생 방문 체크를 해제하고, 팀 완성 여부 체크한다. (이때는 팀이 안되었더라도 그냥 체크를 해준다.)
    visit[n] = false;
    done[n] = true;
}

 

 

🖥 전체 코드

import java.util.*;
import java.io.*;

public class Main{
    static int[] arr;
    static boolean[] visit, done;    // 방문, 팀 편성 완료 배열
    static int count;    // 팀이 완성된 인원 수
    
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(bf.readLine());
        
        StringTokenizer st;
        for(int p = 0; p < T; p++){
            int n = Integer.parseInt(bf.readLine());
            arr = new int[n+1];
            visit = new boolean[n+1];
            done = new boolean[n+1];
            count = 0;
            
            st = new StringTokenizer(bf.readLine());
            
            for(int i=1; i<= n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            
            for(int i=1; i<= n; i++){
                if(!done[i]){
                    dfs(i);
                }
            }
            bw.write((n-count) + "\n");
        }
        bw.flush();
        bw.close();
    }
    
    public static void dfs(int n){
        // 이미 방문 했을 때!
        if(visit[n]){
            done[n] = true;    // 팀 편성 완료했다고 처리
            count++;    // 팀 편성 완료 인원 증가
        }else{
            // 방문하지 않았을 때 -> 방문 처리!
            visit[n] = true;
        }
        
        // 다음 학생이 팀 결성을 아직 못했을 경우
        if(!done[arr[n]]){
            dfs(arr[n]);
        }

        visit[n] = false;
        done[n] = true;
    }
}