[프로그래머스 Lv. 2] 혼자 놀기의 달인

문제

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

접근

그래프 사이클 문제

1) cards 리스트를 단방향 그래프 형태로 만든다.

2) for문으로 모든 노드에 대해 dfs를 돌리는데 이 때 이미 방문한 노드는 넘어간다.

3) dfs에서 맨 처음 방문했던 번호와 현재 번호가 같으면 answer 배열에 상자에 들어있는 번호의 개수를 넣어준다.

4) 내림차순으로 정렬 후, 상자 그룹이 2개 이상일 시 answer[0] * answer[1] 1개 이하면 0으로 값을 반환한다.

Code

from collections import defaultdict

def solution(cards):
    visit = [0] * (len(cards) +1)

    def dfs(start, curr, prev):
        if start == curr and visit[start]:
            answer.append(visit[prev])
            return

        visit[curr] = visit[prev] + 1

        for next_num in graph[curr]:
            dfs(start, next_num, curr)


    answer = []
    graph = defaultdict(list)

    for i in range(1, len(cards) + 1):
        graph[i].append(cards[i-1])
        
    for c in range(1, len(cards) + 1):
        if not visit[c]:
            dfs(c,c,0)

    answer = sorted(answer, reverse=True)
    return answer[0] * answer[1] if len(answer) >= 2 else 0

여담

위와 비슷한 문제 : https://www.acmicpc.net/problem/9466 (텀 프로젝트)