[백준: Java] 9466 - 텀 프로젝트

[문제]

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

문제를 단순하게 표현하면, 형성된 그래프에서 사이클에 속하지 않는 노드의 수를 찾으면 되는 문제입니다. 여기서 노드는 학생을 의미합니다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

문제의 예시를 그래프로 나타내면 다음과 같은 모습을 나타내게 됩니다. 여기서 사이클에 속하지 않는 노드는 1, 2, 5 총 3개가 됩니다.

 

위와 같이 그래프로 표현해 보고, 문제에서 제시하는 바가 사이클에 속하지 않는 노드를 찾아야 한다는 것을 알 수 있었습니다.

 

문제 자체는, BFS와 DFS 모두 수행가능하지만, 최단 경로를 찾는 문제도 아니고 탐색 과정을 추적하는 과정에서 별도의 비용일 발생하는 BFS보다 DFS가 적합하기 때문에, 해당 방식으로 문제를 풀어냈습니다.

 

제 방식이 최적이 아닐 수 있지만, 실제로 BFS와 DFS의 백준 소요 시간이 약 600ms정도 차이가 났습니다.

---

[초기화]

public class BOJ_9466_텀프로젝트 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int t;
    static int n;
    static int[] students;
    static boolean[] visited;
    static boolean[] done;
    static StringBuilder sb = new StringBuilder();
    static int count;

    public static void main(String[] args) throws IOException {
        t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            students = new int[n + 1];
            visited = new boolean[n + 1];
            done = new boolean[n + 1];
            count = 0;

            for (int i = 1; i <= n; i++)
                students[i] = Integer.parseInt(st.nextToken());

            solve();
        }

        System.out.println(sb);
    }

탐색을 수행하기 위한 변수들을 초기화합니다. 입력으로 들어오는 학생들의 정보가 하나의 그래프이므로, 별도로 생성하지는 않습니다.

 

또한 사이클 검사 여부를 확인하기 위한 done 배열도 하나 생성합니다.

---

[풀이]

    static void solve() {
        for (int i = 1; i <= n; i++)
            if (!visited[i])
                dfs(i);

        sb.append(n - count).append("\n");
    }

모든 노드에 대해서 탐색합니다.

 

이후 전체 학생의 수에서 팀을 이룬(사이클에 속하는) 학생의 수만큼 뺀 값이 팀을 이루지 못한 학생들의 수가 됩니다.

    static void dfs(int current) {
        visited[current] = true;
        int next = students[current];  // 다음 노드

        if (!visited[next])  // 다음 노드를 아직 방문하지 않았다면
            dfs(next);
        else if (!done[next])  // 사이클 확인
            find_cycle(next);

        if(!done[current])
            done[current] = true;  // 사이클 탐색 종료
    }

현재 학생이 가리키고 있는 학생의 상태를 확인합니다.

1. 방문하지 않았다면 다음 학생으로 이동
2. 이미 방문한 학생이라면 해당 학생을 기준으로 사이클이 발생했는지 확인

DFS의 특성상 현재 노드를 기준으로 재귀호출이 진행되면서 자기 자신으로 다시 돌아오는 경우가 있습니다.

이때, 사이클을 검사하게 되고 탐색 여부를 갱신하게 됩니다.

 

이후 최종적으로 해당 노드에 대한 탐색이 종료되었으므로, 해당 노드도 갱신합니다.

 

주의할 점은 done 배열은 사이클 유무를 체크하는 게 아닌, 사이클에 포함되어 있는지 검사 유무를 체크하는 배열이라는 점입니다.

 

이를 체크하지 않으면, 사이클이 형성된 노드를 가리키는 노드를 만났을 때, 불필요한 검사를 수행하게 됩니다.

    static void find_cycle(int start) {
        count++;  // 자기 자신
        for (int i = students[start]; i != start; i = students[i])  // 다음 노드가 주어진 start와 다르면
            count++;
    }

사이클에 포함되어 있는 자기 자신을 우선적으로 카운트합니다.

 

이후 자기 자신이 가리키는 다음 노드들로 이동하면서 다시 돌아올 때까지 카운트를 갱신합니다.

---

[전체 코드]

package 백준.골드;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_9466_텀프로젝트 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int t;
    static int n;
    static int[] students;
    static boolean[] visited;
    static boolean[] done;
    static StringBuilder sb = new StringBuilder();
    static int count;

    public static void main(String[] args) throws IOException {
        t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            students = new int[n + 1];
            visited = new boolean[n + 1];
            done = new boolean[n + 1];
            count = 0;

            for (int i = 1; i <= n; i++)
                students[i] = Integer.parseInt(st.nextToken());

            solve();
        }

        System.out.println(sb);
    }

    static void solve() {
        for (int i = 1; i <= n; i++)
            if (!visited[i])
                dfs(i);

        sb.append(n - count).append("\n");
    }

    static void dfs(int current) {
        visited[current] = true;
        int next = students[current];  // 다음 노드

        if (!visited[next])  // 다음 노드를 아직 방문하지 않았다면
            dfs(next);
        else if (!done[next])  // 사이클 확인
            find_cycle(next);

        if(!done[current])
            done[current] = true;  // 사이클 탐색 종료
    }

    static void find_cycle(int start) {
        count++;  // 자기 자신
        for (int i = students[start]; i != start; i = students[i])  // 다음 노드가 주어진 start와 다르면
            count++;
    }
}

---