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

-Code

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

public class BOJ9466 {
    static boolean[] visited;
    static boolean[] finished;
    static int[] students;
    static int answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int test = 0; test < testCase; test++) {
            int cnt = Integer.parseInt(br.readLine());
            // answer init
            answer = 0;
            // visited, finished init
            visited = new boolean[cnt + 1];
            finished = new boolean[cnt + 1];
            // students setting
            StringTokenizer st = new StringTokenizer(br.readLine());
            students = new int[cnt + 1];
            for (int i = 1; i <= cnt; i++) {
                students[i] = Integer.parseInt(st.nextToken());
            }
            // DFS
            for (int i = 1; i <= cnt; i++) {
                if (!visited[i]) {
                    DFS(i);
                }
            }
            System.out.println(cnt - answer);
        }
    }

    private static void DFS(int now) {
        visited[now] = true;
        int next = students[now];
        // 방문하지 않은 경우 탐색
        if (!visited[next]) {
            DFS(next);
        } else if (!finished[next]) {
            // 현재값 +1
            answer++;
            // 방문한 경우 연결된 학생들 세기
            int temp = next;
            while (temp != now) {
                answer++;
                temp = students[temp];
            }
        }
        // 이 노드에서 연결된 다른 노드 탐색 완료 처리
        finished[now] = true;
    }
}

처음에는 visited 하나로 true가 나왔을 경우 answer를 조작했는데 이 경우 연결한 노드 전체 검사가 안되어서 출력이 다르게 나왔습니다.

그래서 이를 어떻게 해결할지 찾아 다음과 같은 2가지 힌트를 얻었습니다.

1. 방문한 노드인 경우 다음 노드부터 현재 노드 도착까지 반복하여 총 노드의 개수를 새줘야 합니다.
2. finished를 하나 더 두고 관련된 노드를 체크하고 finished 처리해주어야 한다는 것을 가지고 해결을 했습니다.

뭔가 DFS의 응용인데 finished라는 또 다른 확인 배열과 다음 학생 노드를 계속 돌면서 새야 하는 방법을 써서 다른 방식의 응용이라 많이 틀렸습니다.