[프로그래머스] 혼자 놀기의 달인 [python]

문제

결국 풀어여 되는 건 간단한데, 문제가 너무 장황하다.

dfs로 사이클이 있는 그래프를 찾고, 그래프의 노드의 수가 많은 것들을 곱하면 되는 문제이다.

dfs로 그래프들을 모두 구한 후, sort를 하고 가장 큰 두 개를 골랐다. 그래프가 하나만 있을 수도 있기 때문에, 미리 0을 넣어서 무조건 두 개의 그래프가 생길 수 있도록 하였다.

 

코드

def solution(cards):
    global cnt
    answers = [0]
    isChecked = [False for i in range(len(cards) + 1)]
    for i in range(1,len(cards) + 1):
        cnt = 1
        if isChecked[i] == False:
            isChecked[i] = True
            dfs(cards, i, isChecked)
            answers.append(cnt)
    tmp = sorted(answers, reverse = True)
    
    return tmp[0] * tmp[1]

def dfs(cards, n, isChecked):
    global cnt
    if isChecked[cards[n-1]] == False:
        isChecked[cards[n-1]] = True
        cnt += 1
        dfs(cards, cards[n-1], isChecked)
    
"""
숫자 카드 더미에는 카드가 총 100장 있으며, 1부터 100까지 숫자가 하나씩, 2이상 100 이하의 자연수를 하나 정해, 그 수부다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며
준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열.
1번부터 순차적으로 증가하는 번호를 붙인다.
상잘르 선택하고 상자 안의 숫자 카드를 확인. 숫자 카드에 적힌 번호에 해당하는 상자를 열어 숫자확인하고 계속 반복
이미 열려있는 상자를 만나면 1번 그룹
다시 또해서, 다음으로 만나면 2번 그룹
1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수
최대 수
모든 케이스 검사하면 될듯 만약 두 개를 열었는데, 닫힌게 없다면 그냥 두 개 곱하고, 비어 있는 게 있다면 BFS한번 더 진행해서 큰 거 고르기
"""