[JAVA] BOJ 백준 9466번 - 텀 프로젝트

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

9466번: 텀 프로젝트

---

2. 내가 푼 방법

사이클을 찾아내기 위한 필수 문제라고 생각한다.

 

이 문제의 핵심은 isDone 변수를 통해 이전에 방문한 적 있는 사람인지 확인하는 것이다. 따라서 사이클을 찾기 위해 텀 프로젝트를 같이 하고 싶은 사람을 타고 들어가면서, 처음 방문하는 경우에는 isVisit 변수를 true로, 두 번째 방문하는 경우에는 isDone 변수를 true로 만들어준다. 만약 텀 프로젝트를 같이 하고 싶은 사람이 이미 방문한 적 있는 사람이라면, 팀을 형성한 상태이거나 혹은 팀을 형성하지 못해 혼자 사이클을 형성했다는 의미이므로 그대로 빠져나온다.

 

최종적으로 cnt는 사이클 개수이므로, 즉 만들어진 팀을 의미한다. 따라서 출력할 때 N - cnt를 해주어야 한다.

public static void solution() {
    for (int i = 1; i <= N; i++) {
        if (!isDone[i]) {
            dfs(i);
        }
    }
}

public static void dfs(int v) {
    if (!isVisit[v]) {
        isVisit[v] = true;
    }
    else {
        isDone[v] = true;
        cnt++;
    }

    if (!isDone[arr[v]]) {
        dfs(arr[v]);
    }

    isVisit[v] = false;
    isDone[v] = true;
}

 

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B9466.java

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

class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static int N;
    static int[] arr;
    static boolean[] isVisit, isDone;
    static int cnt;

    public static void main (String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            input();
            solution();
            output();
        }

        br.close();
        bw.flush();
        bw.close();
    }

    public static void solution() {
        for (int i = 1; i <= N; i++) {
            if (!isDone[i]) {
                dfs(i);
            }
        }
    }

    public static void dfs(int v) {
        if (!isVisit[v]) {
            isVisit[v] = true;
        }
        else {
            isDone[v] = true;
            cnt++;
        }

        if (!isDone[arr[v]]) {
            dfs(arr[v]);
        }

        isVisit[v] = false;
        isDone[v] = true;
    }

    public static void output() throws IOException {
        bw.write(N-cnt+"\n");
    }

    public static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N+1];
        isVisit = new boolean[N+1];
        isDone = new boolean[N+1];
        cnt = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }
}

---

4. 결과 및 회고

비슷한 알고리즘의 응용 버전으로 https://www.acmicpc.net/problem/16724 문제도 풀어보면 좋을 것 같다.ㅎㅎ