[백준 9466번] 텀 프로젝트 :: 늦깎이 IT

[백준 9466번] 텀 프로젝트 URL

1. 사이클에 들어가지 못한 노드들의 갯수를 묻는 문제이다.

2. 우선 1번부터 N번까지의 노드들을 순차적으로 탐색한다.

3. 어느 노드부터 시작해서 방문하지 않았거나 그룹에 속하지 않았을 경우 계속해서 탐색을 진행한다.

4. 이미 방문했거나 그룹에 들어간 노드를 만나면 탐색을 멈추고, 그 노드의 번호를 기억한다.

5. 아래와 같은 입력이 주어졌을 때를 생각해보자.

• 1부터 탐색을 시작해서, 3에서 탐색을 끝낸다. 탐색을 하며 각 노드들을 list에 저장한다.
• 3에서 탐색이 끝나면 cur 에는 3이 저장되어 있다.
• list를 돌면서 처음 시작점과 끝나는 점을 비교한다.
• 시작점 == 끝점(cur)을 찾았으면 그때의 list 인덱스를 저장하고 break문으로 for문을 빠져나온다.
• 저장했던 인덱스부터 list의 끝까지 돌면서 finished를 true로 바꾼다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M, tCase;
    static boolean[] visited, finished;
    static int[] student;
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            visited = new boolean[N + 1];
            finished = new boolean[N + 1];
            student = new int[N + 1];
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++)
                student[i] = Integer.parseInt(st.nextToken());
 
            solve();
            int ans = 0;
            for (int i = 1; i <= N; i++) {
                if (!finished[i])
                    ans += 1;
            }
            System.out.println(ans);
        }
    }
 
    public static void solve() {
 
        for (int i = 1; i <= N; i++) {
 
            if (visited[i] || finished[i])
                continue;
 
            List<Integer> list = new ArrayList<>();
            int cur = i;
 
            while (!visited[cur] && !finished[cur]) {
                visited[cur] = true;
                list.add(cur);
                cur = student[cur];
            }
            int idx;
            for (idx = 0; idx < list.size(); idx++) {
                if (list.get(idx) == cur)
                    break;
            }
 
            for (; idx < list.size(); idx++) {
                finished[list.get(idx)] = true;
            }
 
        }
 
    }
}