백준 9466 (텀 프로젝트)

문제

9466번: 텀 프로젝트

N개의 노드의 단방향 그래프 정보가 주어지면 사이클을 포함한 노드를 제외하고 노드가 몇개 있는지 구하는 문제이다.

노드는 항상 한개의 노드만 가리킬 수 있다.

---

처음 접근은 다음과 같다.

N개의 노드마다 dfs를 진행하고, 처음 시작한 노드 번호가 사이클을 이룰 수 있는지 없는지 판단하는 것이다.

따라서 최악의 경우 N^2의 시간 복잡도를 갖게 된다.

public class Main {
    private static int []list;
    private static int[]state;
    private static boolean[]isCycle;
    private static int cnt;
    private static boolean check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        while(t-- >0){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            list = new int[n+1];
            isCycle = new boolean[n+1];
            state = new int[n+1];
            st = new StringTokenizer(br.readLine());
            for(int i = 1;i<=n;i++){
                list[i] = Integer.parseInt(st.nextToken());
            }

            int ans=0;
            for(int i=1;i<=n;i++){
                if(isCycle[i])continue;
                //state = new int[n+1];
                cnt=0;
                check=false;
                if(state[i] != 1)dfs(i, i);

                if(check){
                    ans+=cnt;
                }
            }
            System.out.println(n-ans);
        }
    }
    private static void dfs(int init, int vertex){
        cnt++;
        state[vertex] = -1;
        int nxt = list[vertex];

        if(state[nxt] == 1)return;

        if(nxt == init){
            check=true;
            isCycle[vertex]=true;
            state[vertex]=1;
            return;
        }

        if(state[nxt]==0){
            dfs(init, nxt);
        }

        if(check){
            isCycle[vertex]=true;
            state[vertex]=1;
        }
        else state[vertex] = 0;

    }
}

내가 처음에 작성한 코드이다.

80%에서 계속 시간 초과가 나왔다.

사이클이 완성된 노드는 dfs를 진행하지 않았음에도 시간초과가 나왔다.

---

두번째 접근 방식이다.

마찬가지로 모든 노드에 대해서 dfs를 진행할 것이다.

하지만 처음 시작한 노드가 사이클이 아니더라도 중간에 사이클이 생기면 사이클을 판별해 나중에 방문을 안할 수 있다.

예를 들어 1 -> 3 -> 3 이런식으로 노드가 연결되어 있다면 1번 노드에서 시작하였지만, 3번 노드가 자기 자신 끼리 사이클을 이루고 있으므로 여기서 사이클을 판별 할 수 있다.

 

이전 코드에서는 1 -> 3 -> 3 이라면 1번 노드에서 시작하는 사이클은 존재하지 않으므로 dfs를 탈출하고, 나중에 3번 노드에서 시작하는

dfs를 따로 실행해주었지만 이 코드는 그럴 필요가 없다. 

1번 노드에서 시작해서 자기자신이 사이클에 포함되지 않더라도 사이클을 판별해 3번 노드를 시작으로하는 dfs를 나중에 실행할 필요가

없게 된것이다.

즉, N의 시간복잡도를 갖게 된다.

public class Main {
    private static int []list;
    private static boolean[]isVisit; //단순히 방문 여부 체크
    private static boolean[]isDone; // 완전히 사이클 형성 여부까지 체크
    private static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        while(t-- >0){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            list = new int[n+1];
            isDone = new boolean[n+1]; 
            isVisit = new boolean[n+1];
            st = new StringTokenizer(br.readLine());
            for(int i = 1;i<=n;i++){
                list[i] = Integer.parseInt(st.nextToken());
            }

            ans=0;
            for(int i=1;i<=n;i++){
                if(isVisit[i])continue;
                dfs(i);
            }
            System.out.println(n-ans);
        }
    }
    private static void dfs(int vertex){
        isVisit[vertex]=true; //일단 방문
        int nxt = list[vertex]; //그 다음에 방문 할 노드

        if(!isVisit[nxt])dfs(nxt); //다음 노드가 방문하지 않았다면 방문
        else if(!isDone[nxt]){ //이전에 방문은 했는데 다시 만났으므로 사이클이다!!
            for(int i = nxt;i != vertex; i = list[i])
                ans++; //사이클을 순회하면서 세기
            ans++; //자기 자신 까지 세어줘야 한다.
        }
        isDone[vertex]=true; //다 완료 되었다면 체크
    }
}