백준 - 10451 - 순열 사이클

www.acmicpc.net/problem/10451

10451번: 순열 사이클

import java.util.*;

public class 순열_사이클 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
        List<Integer> results = new ArrayList<>();

        for(int t=0; t<T; t++) {
            int N = Integer.parseInt(sc.nextLine());
            List<String> nodes = new ArrayList<>();
            nodes.add(0, null);
            List<String> temp = new ArrayList<>(Arrays.asList(sc.nextLine().split(" ")));
            nodes.addAll(temp);
            results.add(countCycle(nodes));
        }

        for(int result : results) {
            System.out.println(result);
        }
    }

    public static int countCycle(List<String> nodes) {
        boolean[] isCycle = new boolean[nodes.size()];
        int cycleCount = 0;

        for (int i = 1; i < nodes.size(); i++) {
            // 방문한 노드가 이미 사이클일 경우 다음 노드 진행
            if(isCycle[i]) {
                continue;
            }

            //방문노드 체크 set
            Set<Integer> visitNodes = new HashSet<>();
            int curNode = i;
            //현재노드 방문처리
            visitNodes.add(i);

            //노드 순회 하면서 사이클 찾기
            while (true) {
                int nextNode = Integer.parseInt(nodes.get(curNode));

                //1.다음 노드가 없는 경우 -> 사이클이 아니다.
                if(nodes.get(nextNode) == null) {
                    break;
                }

                //2.다음 노드가 이미 사이클인 경우 -> 현재 노드도 사이클로 세팅
                if(isCycle[nextNode]) {
                    isCycle[i] = true;
                    break;
                }

                //3.다음 노드가 이미 방문했던 노드인 경우 -> 사이클임을 확정. -> 사이클로 세팅
                if(visitNodes.contains(nextNode)) {
                    for(int visitNode : visitNodes) {
                        isCycle[visitNode] = true;
                    }
                    cycleCount++;
                    break;
                }

                //4.아무 경우도 아닌 경우 다음 노드로 진행
                curNode = nextNode;
            }
        }

        return cycleCount;
    }
}

문제

순열을 배열로 표현한 것을 그래프로 표현했을때 사이클이 생길수 있다. 이때 사이클의 개수는 몇 개인가?

 

알고리즘: 완전 탐색(brute force)

• 노드 리스트를 입력받아 순회하면서 사이클의 갯수를 확인한다.
• 다음 노드의 상태를 체크해보면 4가지의 경우가 있다.
• 1. 다음 노드가 없는 경우 -> 사이클이 아니기 때문에 넘어간다.
• 2. 다음 노드가 이미 사이클인 경우 -> 현재 노드도 결국 다음 노드로 진행했을 경우 사이클로 빠지게 되므로 현재 노드도 사이클로 기록한다.
• 3. 다음 노드가 이미 방문했던 노드인 경우 -> 새로운 사이클을 발견했다. 사이클 갯수를 +1 해주고 다음 노드로 진행한다.
• 4. 1,2,3번의 경우가 아닌 일반적인 경우 -> 아직 사이클인지 사이클이 아닌지 판단할 수 없음으로 다음 노드의 다음노드를 체크해본다.

성능

• 시간 복잡도: O(N^3) 성능이 안좋다..최악의 경우를 생각해보면 입력받은 노드들이 아주 커다란 한개의 사이클로 구성되어있다고 한다면 N*N*N이 된다.
• 공간 복잡도: O(N)

주의할점

brute force로 진행할 경우 시간 초과가 나올 수 있다.

원래는 방문체크를 배열로 선언해서 배열을 순회하며 방문했는지 체크를 했는데 시간 초과로 HashSet을 이용하여 성능을 개선했다.