[백준 9466, Java] 텀프로젝트

문제

www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

풀이1(시간초과)

node를 순회하면서 각 노드에 대해 처음 탐색을시작하는 노드와 탐색이 종료되는 노드가 같으면 팀을 이루고, 다르면 팀이 아니다. 

 

 위의 표를 예로 들어보자.

node 1에 대해서 탐색을 시작한다. 그러면 차례대로 1->3->3 을 방문하게 되는데, 3의 다음노드는 3이고, 이는 이미 방문했던 노드이므로 1->3 ->3에서 탐색을 종료한다. 이때 탐색시작노드 1과 탐색 마지막 노드 3이 다르므로 1은 팀원이 아니다.

 

node 4에 대해서 탐색을 시작한다. 차례대로 4->7->6 ->4를 방문하게 되고 시작노드 4와 끝노드 4가 같으므로 4는 팀원이 된다. 

 

 위의 로직을 bfs로 구현했는데, 이떄의 시간복잡도는 N*N 이 된다. 최악의 경우 1->2, 2->3, N-1->N, N->1인 경우 모든 노드 N개에 대해서 N번 순회하기 때문이다. N = 10^5 이므로 시간복잡도는 10^10인데 1억을 초과하므로 시간초과가 난다.

 

 

 

풀이2

시간을 줄이려면 한번 순회할 때 탐색한 노드들에 대한 방문처리를 해서, 다음 탐색노드가 이미 방문한 노드를 방문하지 않게 해야한다. 

 

각 노드에 대해서 방문노드를 나열하면 아래와 같다. 

1->3->3

2->1->3->3

3->3

4->7->6->4

5->3->3

6->4->7->6

7->6->4->7

 

위를 보면, 순환이 발생하면 탐색을 종료한다. 순횐이 일어났다는 것은 순환이 일어난 노드끼리 팀을 이룬다는 뜻이다.  또한 2->1->3->3에서 2->1인 경우 1->3->3에서 이미 팀인지 아닌지를 체크했으므로 다시방문할 필요가 없다. 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;


public class Main {
    public static int T;
    public static int N;
    public static int[] linking;
    public static boolean[] visited;
    public static boolean[] finished;
    public static int teamCount;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for(int t=0; t<T; t++){
            N = Integer.parseInt(br.readLine());
            linking = new int[N+1];

            st = new StringTokenizer(br.readLine()," ");
            for(int i = 1; i<N+1; i++){
                linking[i] = Integer.parseInt(st.nextToken());
            }

            finished = new boolean[N+1];
             visited = new boolean[N+1];
            teamCount = 0;
            for(int node  =1 ; node<=N ; node++){
               
                dfs(node);
            }
            bw.write(String.valueOf(N-teamCount)+"\n");
        }
        bw.flush();
    }
    public static void dfs(int node){
        visited[node] = true;
        int nextNode = linking[node];

        if(!visited[nextNode]){
            dfs(nextNode);
        }
        else{
            if(!finished[nextNode]){
                ++teamCount;
                while(nextNode!=node){
                    ++teamCount;
                    nextNode = linking[nextNode];;
                }
            }
        }
        finished[node] = true;
    }
}

 

 

comment

 한번에 못풀고, 블로그 보고도 이해 못하다가 스터디하면서 겨우 이해했다. 이런문제 언젠간 한번에 풀 수 있겠지?