[백준/JAVA] 9466번: 텀 프로젝트

🔺 문제

9466번: 텀 프로젝트

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    
    static int[] arr;
    static boolean[] visited, done; // 방문, 팀 편성 완료 배열
    
    static int cnt;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            int N = Integer.parseInt(br.readLine());
            
            arr = new int[N + 1];
            visited = new boolean[N + 1];
            done = new boolean[N + 1];
            cnt = 0;
            
            st = new StringTokenizer(br.readLine(), " ");
            for(int i = 1 ; i <= N ; i++) {
                int num = Integer.parseInt(st.nextToken());
                arr[i] = num;
            }
            
            for(int i = 1 ; i <= N ; i++) {
                if(!done[i]) {
                    dfs(i);
                }
            }
            
            sb.append(N - cnt).append("\n");
        }
        
        System.out.println(sb);
        
    }
    
    private static void dfs(int num) {
        if(visited[num]) { // 이미 방문한 경우
            done[num] = true; // 팀 편성 완료 처리
            cnt++;            // 팀 편성 완료 인원 증가
        }
        else {
            visited[num] = true;
        }
        
        // 다음 학생이 팀 결성을 아직 못 했을 경우
        if(!done[arr[num]]) {
            dfs(arr[num]);
        }
        
        visited[num] = false; // 학생 방문 체크 초기화
        done[num] = true; // 모든 작업이 끝나서 더 이상 사용하지 않음 (사이클이 아닌 애들 위해 여기에 작성)
    }
}

✅ 해결 아이디어
✔ DFS
- 사이클을 만들지 못 하는 노드 개수 찾기

🧩 필요한 자료구조

- visited[] : 방문 여부 체크용 배열 배열

- done[]    : 팀 완성 배열

 

 

💥 유의사항

• 모든 점에 대해 DFS 수행 시, 시간 복잡도가 O(n^2)이 되어 시간 초과

 

 

---

💬 느낀 점

유니온파인드로도 풀 수 있지 않을까? 생각했는데

이미 그렇게 풀어본 분이 계시고, 시간초과가 발생한다고 한다. (참고)

 

복습을 잘해야겄다,,,

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 친절한 해설과 주석.. 감사합니다...

백준 9466번. 텀 프로젝트 (Java)

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

 

[BOJ] 백준 9466번 텀 프로젝트 (Java)

 

- 복습용

[백준] 9466번 텀 프로젝트 (JAVA)