[백준 9466 : JAVA] 텀 프로젝트 / DFS

문제

---

 

 

 

풀이

---

이 문제는 모든 정점은 한 번씩만 탐색되어야 한다는게 핵심이다. 첫 번째 예제를 살펴보자.

 

[그림 1] 첫 번째 예제 입력에 대한 그림

 

가장 먼저 1번 노드부터 탐색을 진행한다.

[그림 2] 첫 번째 탐색

 

1번 노드부터 탐색을 시작했더니 3번 노드가 사이클을 형성한다는걸 찾았다.

이게 이 문제의 포인트인데, 사이클 형성 여부를 찾기 위해 가장 쉽게 생각해볼 수 있는 방법은 다음과 같다.

• 처음 탐색을 시작한 노드 == 마지막으로 탐색할 노드 

 

위의 방법으로 탐색을 진행하게 된다면 중복 탐색이 많이 발생하게 된다는 단점이 있다.

1번 노드가 사이클이 형성되지 않는단 걸 알지만, 다음 2번 노드의 탐색을 진행할 때 2 - 1 -3 으로 1번과 똑같은 탐색을 진행하게 된다.

다음 그림을 보자.

 

조건을 아래와 같이 바꾼다.

다음 노드가 탐색 시작 노드와 같은지 ---------> 다음 노드가 탐색을 통해 거쳐왔던 노드 중 하나와 같은지 

private static int dfs(int start, int current, int depth) {
    
    // ...중략
    
    if (check[next] != 0) { 
        if (start == firstParent[next]) return depth - check[next] + 1;
        else return 0;
    }

    // ...중략 
}

 

 

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int T;
    private static int[] edge;
    private static int[] check;
    private static int[] firstParent;

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

        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            firstParent = new int[n + 1];
            check = new int[n + 1];
            edge = new int[n + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++)
                edge[j] = Integer.parseInt(st.nextToken());

            int count = 0;
            for (int i = 1; i <= n; i++) {
                if (check[edge[i]] == 0)
                    count += dfs(i, i, 1);
            }

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

        br.close();
    }

    private static int dfs(int start, int current, int depth) {
        check[current] = depth;
        firstParent[current] = start;

        int next = edge[current];

        if (check[next] != 0) { // 방문했던 노드라면, 다음에 방문할 노드를 확인하여 사이클 형성 여부를 확인한다.
            if (start == firstParent[next]) return depth - check[next] + 1;
            else return 0;
        }

        return dfs(start, next, depth + 1);
    }
}