[BOJ] 9466: 텀 프로젝트 (JAVA)

문제

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

 

여담

처음에 BFS 방식으로 사이클을 찾으려고 했다가 계속 시간초과가 발생했다. 찾아보니 사이클을 판별할 때는 DFS 탐색을 사용해야 한다고 한다.. 그래프 탐색으로 사이클을 찾을 때는 DFS 탐색 & 배열 2개를 기억하자!

 

풀이

프로젝트를 함께 하고 싶은 학생을 선택한 것을 연결했을 때, 사이클이 발생하면 하나의 팀을 구성할 수 있다.

• 1번 학생이 2번 선택, 2번 학생이 3번 선택
  • 1 → 2 → 3 ... (단방향)

 

사이클을 탐지하기 위해 DFS 탐색 시 방문 여부를 기록하는 visited 배열과 팀 구성 여부를 기록하는 check 배열, 즉 총 2개의 배열을 생성해야 한다.

 

우선 선택의 결과를 입력받고 팀 구성이 완료되지 않은 학생만 DFS 탐색을 수행하면 된다. 이때, 자신이 자신의 선택한 경우도 팀이 구성된 것이므로, 팀 구성 완료 처리를 해주면 된다. 

 

DFS 탐색 과정은 다음과 같다.

1. 확인하는 학생의 팀 구성이 완료된 경우라면 탐색을 종료하기
2. 팀 구성이 완료되지 않았고, 이미 방문한 경우라면 사이클이 생성된 것
   
   • 팀 구성 완료 처리하기: check[x] = true
3. 처음 방문한 경우라면, 방문 처리를 한 뒤 DFS 탐색하기 (재귀호출)
4. DFS 탐색이 끝나기 전, 사이클에 포함되지 않더라도 팀 구성 여부를 확인했으므로 상태 변경하기

 

자세한 내용은 아래의 코드를 참고하면 된다.

 

코드

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

public class Main {
    static int N, answer;
    static int[] students;
    static boolean[] check, visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            students = new int[N + 1];
            check = new boolean[N + 1];
            visited = new boolean[N + 1];
            answer = N;

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= N; i++) {
                students[i] = Integer.parseInt(st.nextToken());
                if (students[i] == i) { // 자기 자신과 팀을 이루는 경우
                    check[i] = true;
                    answer--;
                }
            }

            for (int i = 1; i <= N; i++) {
                if (!check[i]) {
                    dfs(i);
                }
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb.toString());
    }

    static void dfs(int x) {
        if (check[x]) return; // 이미 사이클 여부를 확인한 곳은 탐색할 필요 X
        if (visited[x]) { // 이미 방문한 지점을 방문한 경우
            answer--;
            check[x] = true;
        }

        visited[x] = true;
        dfs(students[x]);
        visited[x] = false;

        check[x] = true; // 팀을 구성하지 않았어도, 사이클 여부를 확인했으므로 true로 변경
    }
}

---

참고

https://iseunghan.tistory.com/317

https://yeeybook.tistory.com/147