[Programmers] Level 2. 혼자 놀기의 달인

🔗 Problem Link

프로그래머스

---

❔Thinking

• 상자를 열어서 해당 상자 안에 있는 숫자에 해당하는 상자를 연속적으로 열어나간다.
• 한번에 열 수 있는 상자의 수를 기록하고, 더이상 열 수 있는 상자가 없을 때까지 상자를 선택하여 연다.
• 한번에 연 상자들을 그룹화할때, 두 개의 그룹의 상자 수를 최대로 한 경우를 반환한다. 그룹이 하나라면 0이다.

---

💻Solution

def solution(cards):
    answer = []
    visited = [False] * len(cards)
    
    def dfs(num:int):
        cnt = 0
        cur = num
        while visited[cur] is False:
            visited[cur] = True
            cnt += 1
            cur = cards[cur] - 1
        return cnt
    
    for i in range(len(cards)):
        if visited[i] is False:
            answer.append(dfs(i))
    answer.sort()
    return answer[-1]*answer[-2] if len(answer) > 1 else 0

---

🗝️keypoint

1. DFS로 상자의 숫자를 확인하여 해당 번호의 상자를 열어나가고, 이미 연 상자라면 멈춘다.
2. 그룹이 하나라면 답은 0이고, 하나 이상이라면 가장 큰 두 수를 곱하여 반환한다.
3. 상자의 개수가 100개 이기 때문에, DFS로도 충분히 해결할 수 있다.