[BOJ] 9466. 텀 프로젝트

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

접근 방법

처음에는 모든 경로에 대해서 파악을 했었는데

중간결과로 시간초과를 했었기에 한가지 생각을 했었다.

즉, 문제를 다시보고 모든 경로에 대해서 마지막은 Cycle을 도는 것을 알게 되었고 코드를 수정하게 되었다.

Ex) 1에서 시작하면 1→3→3 ( Cycle )

  2에서 시작하면 2→1→3→3 (Cycle) 

초기에는 1 , 2 , 3 을 모두 다 체크해서 {3}이라는 Cycle을 찾았지만 코드를 수정하고 1에서 {3}이라는 Cycle을 찾을 수 있었다.

Need Know

1. Recursive

전체 코드 ( Java )

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

class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int T;
    static int N;
    static int[] map;
    static boolean[] isTeam;
    static boolean[] visit;
    static int count;
    public static void main(String[] args) throws IOException {
        set();

        bw.flush();
    }
    static void set() throws IOException {
        T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            N = Integer.parseInt(br.readLine());
            map = new int[N+1];
            isTeam = new boolean[N+1];
            visit = new boolean[N+1];
            count = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int k=1; k<N+1; k++){
                map[k] = Integer.parseInt(st.nextToken());
            }
            solve();
        }
    }
    static void solve() throws IOException{
        for(int i=1; i<N+1; i++){
            dfs(i);
        }
        bw.write((N-count) +"\n");
    }
    static void dfs(int now) {
        if(visit[now]){
            return;
        }

        visit[now] = true;
        int next = map[now];

        if(!visit[next])
            dfs(next);
        else {
            if(!isTeam[next]) {
                count++;
                for(int i=next; i != now; i = map[i]){
                    count++;
                }
            }
        }
        isTeam[now] = true;
    }
}