[백준] 9466. 텀프로젝트

(1) 재귀 체크

• 그래프 문제는 아니다.
• 사이클을 찾는 문제다.
• 단독 사이클이 가능하므로, 이 원소와 연결되는 애들은 같은 팀이아니다.

import java.awt.*;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

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

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

        for (int t = 0; t < T; t++) {
            int n = Integer.parseInt(br.readLine()); // 10만

            StringTokenizer st = new StringTokenizer(br.readLine()); // 선택한 번호, 1부터 시작

            selected = new int[n + 1]; // 정
            visited = new boolean[n + 1];
            result = 0;
            isChecked = new boolean[n + 1];

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


            for (int i = 1; i <= n; i++) {
                if (!isChecked[i]) {
                    dfs(i);
                }
            }

            System.out.println(n - result);
        }

        bw.flush();
        bw.close();
        br.close();
    }
    static int[] selected;
    static int result;
    private static void dfs(int x) {
        // 이미 체크함.
        if (isChecked[x]) return;

        // visited의 목적은 재방문 찾기. 사이클 찾기임.
        // 이문제의 특징은 무조건 사이클이 탄생한다는것.
        // 이미 방문한 곳을 만나면 -> 사이클임.
        if (visited[x]){ // 이 조건문 덕분.
            isChecked[x] = true;
            result++; // 사이클일때만 다시돌아와서 ++.
        }
        // 방문하지않았으면
        visited[x] = true;
        dfs(selected[x]);
        // 여기다 result++ 넣으면 사이클 아닌것들도 다 걸림.
        isChecked[x] = true; // 사이클 아닌것들도 근데 검사 끝났으니까 ischecked.
        visited[x] = false; // 매번 초기화 해주면 시간초과 난다고함.
    }
    static boolean[] visited;
    static boolean[] isChecked;
}

• 일단 처음접근은 모든 점마다 dfs를 돌렸는데, 당연히 시간초과가 났다.

• 기본틀은 dfs가 맞는데, 시간초과가 안나도록 조건문, 체크 배열을 추가할 필요가 있다.

  • 체크배열 (isChecked)
    1. 이미 검증이 끝난 원소들은 다시 반복해서 들어가지않는다.
    2. 즉, 예제의 2 -> 1 -> 3 -> 3 으로 이루어진 것들도 단독사이클을 포함한 사이클(?) 이므로 체크해둔다.
       (dfs 아래 isChecked문이 존재하는 이유이다. 이게 빠지면 시간초과난다.)
    3. 이 배열은 마지막에 true만 골라다가 count하게 셀수없다.
    4. 따라서 dfs안에 count문을 따로 두어 체크한다.
  • 방문배열(visited)
    1. 평소에 쓰던 방문처리용보다 약간 특별한 의미를 가진다.
    2. 4->7->6->4 로 순환하는 사이클에서
       (visited) -> (visited) -> (visited) -> (4번째 visited)
       4번째 visited를 통해 사이클을 판별하는 기능을 한다.
       이후, return문 처리를 하지않고, 다음 dfs로 넘어가, isChecked처리를 하지않았으므로, 모두 isChecked처리를 해주면서 같은 팀 원소들을 count한다.

• 즉, 시간을 줄이기위한 방법을 정리하면

1. visited
2. isChecked
   두가지이다.