https://school.programmers.co.kr/learn/courses/30/lessons/131130

---

1. 코드

from collections import defaultdict


def solution(cards):
    def dfs(key, visited):
        if d[key] == start:
            result.append(len(visited))
            # 1 -> 8 -> 4 -> 7 -> 1 이후에는 set 자료형인 used에 
            # 1, 8, 4, 7을 추가해줘서 다음 for문에서 만났을 경우 스킵할 수 있다.
            for v in visited:
                used.add(v)
        else:
            dfs(d[key], visited + [d[key]])

    result = []
    d = defaultdict(int)

    for i in range(1, len(cards)+1):
        d[i] = cards[i-1]

    used = set()
    for start in range(1, len(cards)+1):
        if start not in used:
            dfs(start, [start])

    result.sort(reverse=True)
    if len(result) == 1:
        return 0
    else:
        return result[0] * result[1]

2. 후기

노트에 적고 print()를 찍어보다가 규칙을 찾아서 풀어봤는데 답이 나왔다.
이 문제처럼 idx와 num의 길이와 set이 일치한다면 아래의 규칙이 적용된다.

idx=1 2 3 4 5 6
num=3 4 5 6 1 2

싸이클1(1, 3, 5)
1->3->5->1
3->5->1->3
5->1->3->5

싸이클2(2, 4, 6)
2->4->6->2
4->6->2->4
6->2->4->6

싸이클을 형성할 경우 싸이클을 이루는 원소들은 항상 자기 자신으로 돌아오는 싸이클을 가지게 된다.

[백준 2668번] 숫자 고르기 문제와 매우 유사하다.