1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import java.util.*;

/*
시간: 35분 (문제파악: 15분, 설계: 10분, 구현: 10분)
 - 지문이 길고 이상해서 문제파악 및 설계에 시간이 오래걸림

유형:
 Goal: 이 게임에서 얻을 수 있는 최고점 구하기
 내풀이1. 택배상자들의 집합을 만들어야 함에 힌트를 얻어 Union-Find로 진행.

 다른사람2. 재귀 or 반복문
 cards에는 중복되는 원소가 존재하지 않음. -> 반드시 사이클이 존재함 -> 어느 박스에서 시작하든 같은 결과임
 이거를 파악 못해서 재귀 or 반복문으로 접근하지 않았음. 문제 꼼꼼히 읽을 것
*/

class Solution {
    private static int count;
    private static int[] parent;
    public int solution(int[] cards) {
        // int answer = solveByUnionFind(cards);
        // int answer = solveByLoof(cards);
        int answer = solveByRecursive(cards);
        return answer;
    }

    private int solveByRecursive(int[] cards) {
        boolean[] visited = new boolean[cards.length];
        List<Integer> answer = new ArrayList<>();
        for(int card: cards) {
            card = card - 1;
            if(!visited[card]) {
                count = 1;
                visited[card] = true;
                recursive(card, cards, visited);
                answer.add(count);
            }
        }
        if(answer.size() == 1) {
            return 0;
        }
        Collections.sort(answer, Comparator.reverseOrder());
        return answer.get(0) * answer.get(1);
    }

    private void recursive(int cur, int[] cards, boolean[] visited) {
        // recur:
        int next = cards[cur] - 1;
        if(!visited[next]) {
            visited[next] = true;
            count++;
            recursive(next, cards, visited);
        }
    }

    /*조건: cards에는 중복되는 원소가 존재하지 않는다. 
    해당 조건에 의해 사이클만 존재함을 알 수 있고, 
    어느 지점에서 시작해도 같은 count를 얻음을 알 수 있으므로
    loof로 해결해도 됨.
    */
    private int solveByLoof(int[] cards) {
        List<Integer> answer = new ArrayList<>();
        boolean[] visited = new boolean[cards.length];
        for(int card: cards) {
            int count = 0;
            card = card - 1;
            while(!visited[card]) {
                visited[card] = true;
                count++;
                card = cards[card] - 1;
            }
            answer.add(count);
        }
        if(answer.size() == 1) {
            return 0;
        }
        Collections.sort(answer, Comparator.reverseOrder());
        return answer.get(0) * answer.get(1);
    }

    private int solveByUnionFind(int[] cards) {
        // union-find로 연결된 택배상자들을 모두 연결한다.
        initialParent(cards.length);
        for(int i=0; i<cards.length; i++) {
            int boxA = i+1;
            int boxB = cards[i];
            union(boxA, boxB);
        }
        // 각 택배상자 집합의 대표인 루트노드의 개수를 기록한다.
        Map<Integer, Integer> rootAndCount = new HashMap<>();
        for(int box=1; box<=cards.length; box++) {
            int root = find(box);
            rootAndCount.put(root, rootAndCount.getOrDefault(root, 0) + 1);
        }
        // 루트노드가 한개인 경우 0이다.
        if(rootAndCount.size() == 1) {
            return 0;
        }
        // 루트노드가 두개 이상인 경우, 큰 값 2개를 곱한다.
        List<Integer> temp = new ArrayList<>();
        for(int root: rootAndCount.keySet()) {
            temp.add(rootAndCount.get(root));
        }
        Collections.sort(temp, Comparator.reverseOrder());
        int answer = temp.get(0) * temp.get(1);
        return answer;
    }

    private void initialParent(int N) {
        parent = new int[N+1];
        for(int box=1; box<=N; box++) {
            parent[box] = box;
        }
    }

    private void union(int boxA, int boxB) {
        int rootA = find(boxA);
        int rootB = find(boxB);
        if(rootA!=rootB) {
            parent[rootA] = rootB;
        }
    }

    private int find(int box) {
        if(parent[box] == box) {
            return box;
        }
        return parent[box] = find(parent[box]);
    }
}