9466번(사이클 찾기)

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

9466번: 텀 프로젝트

이 문제는 너무 어려웠다..

그래서 결국 해설을 봤다.. 처음에 내가 구현한 방법은 단순히 모든 DFS를 다 돌아서 사이클을 찾아내는 방식으로 했다. 그래서 시간초과가 났다.

그래서 시간초과를 해결하기 위해서는 사이클이 있는 경우 사이클을 이루는 갯수를 세고, 이 과정에서 사용한 노드는 더 이상방문할 필요없는 노드로 처리하여 중복적으로 탐색하는 것을 막아야 했다.

예를 들어 2->1->3->3과 1->3->3의 경우 같은 3->3사이클에서 끝이 난다. 그렇다면 두 경우 모두 동일한 사이클을 찾는 경우이기 때문에 한번만 진행하면 된다. 따라서 1->3->3을 처리하면서 사이클을 처리한 노드를 따로 모아서 저장하는 방식으로 처리했다.

1과 3을 사이클처리 set에 넣고 다음으로 2->1->3->3에서는 1이 이미 사이클처리가 끝났음으로 탐색을 중지한다.

그리고 2 또한 사이클처리 set에 넣는다. 그리고 3 또한 이미 처리 했음으로 넘어가고, 4를 탐색하면 4->7->6->4로 사이클을 돈다. 따라서 사이클 구성 요소의 갯수를 세고 모두 사이클 처리 set에 넣는다. 그러면 사이클 처리 set에는 1,2,3,4,6,7이 들어있고, 다음으로 5를 방문하면 인접노드 3은 이미 사이클 처리했음으로 끝내고 6과 7로 넘어가는데 6,7 또한 이미 사이클 처리 set에 들어있음으로 끝낸다.

 

이렇게 중복적으로 같은 사이클을 찾는 경우를 제외시켜서 시간을 단축시켜 문제를 해결했다.

왜 이 생각을 못했는지...아직 많이 부족하다...더 공부해야겠다.

 

그래서 정리하자면, 중복적으로 동일한 한 사이클을 찾는 경우를 배제하기 위해서 사이클 처리 set을 정의하고, 하나의 사이클을 처리하는데 사용된 노드들은 모두 set에 넣고 다시 사용하지 않는다. 이를 반복하면서 사이클에 사용된 요소 수를 세어 전체 요소 수에서 빼서 정한다.

정답 코드는 아래와 같다.

package backjoon.b9466;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class b9466 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<test; i++){
            int N = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            Graph g =new Graph(N);
            for(int j=1; j<=N; j++){
                g.addEdge(j, Integer.parseInt(st.nextToken()));
            }
            int count = 0;
            for(int j=1; j<=N; j++){
                if(!g.visit[j]){
                    g.dfs(j);
                }
            }
            sb.append(N-g.count).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    boolean[] visit;
    boolean cycle=false;
    LinkedList<Integer>[] adj;
    int N;
    HashSet<Integer> cycleSet;
    int count;

    public Graph(int n) {
        N = n;
        adj = new LinkedList[n+1];
        visit = new boolean[n+1];
        for (int i=0; i<=n; i++) {
            adj[i]=new LinkedList<>();
        }
        cycleSet = new HashSet<>();
    }

    public void addEdge(int u, int v){
        adj[u].add(v);
    }

    public void dfs(int R){
        visit[R]=true;
        for(int i : adj[R]){
            if(!visit[i]){
                visit[i]=true;
                dfs(i);
            }//방문하지 않은 인접노드면 방문
            else {//방문했던 인접노드
                if(!cycleSet.contains(i)){
                    int next = i;
                    while (next!=R) {
                        count++;
                        next = adj[next].get(0);
                    }
                    count++;//싸이클의 시작점을 찾았으니 사이클에 있는 값들을 센다.
                }
            }
        }
        cycleSet.add(R);//더이상 탐색할 필요없는 노드를 넣는다.
    }
}