알고리즘 코드카타 125- 혼자 놀기의 달인

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

프로그래머스

문제 설명
혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

제한사항
2 ≤ cards의 길이 ≤ 100
cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
cards에는 중복되는 원소가 존재하지 않습니다.
cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

 

입출력예시

cards	result
[8,6,3,7,2,5,1,4]	12

 

 

문제를 살펴보면 각 상자의 인덱스가 다른 상자의 인덱스들을 가르키고 있다는 것을 알 수 있다. 그러므로 각 그룹은 서로가 모두 연결된 그래프의 형태라고 할 수 있다.

입출력 예시의 그래프

 

따라서 각 노드별로 해당 노드가 속한 공간을 탐색하고 그 노드가 속한 그래프의 모든 노드의 수를 반환하여 가장 큰 두 값을 곱해서 출력하면 된다.

 

def solution(cards):
    dict_cards = {i+1:v for i, v in enumerate(cards)}
    group_1 = 0
    group_2 = 0

 

간편한 탐색을 위해서 주어진 리스트를 딕셔너리 형태로 변환한다.

그리고 그룹내의 노드를 가장 많이 가지고 있는 그룹의 노드의 수를 저장할 group_1과 그 다음으로 많은 그룹의 노드의 수를 저장할 group_2를 초기화한다.

 

def bfs(graph, start):
    explore = [start]
    
    for node in explore:
        if graph[node] not in explore:
            explore.append(graph[node])
    return explore, len(explore)

 

다음으로 dict_cards를 탐색하기 위한 bfs함수를 작성한다. 탐색한 그래프와 탐색을 시작할 위치를 인자로 받는다.

탐색할/탐색을 마친 노드는 explore에 순서대로 저장하고 현재 노드와 연결된 노드를 explore추가한다. 이때, 이미 탐색한 노드인 경우에는 explore에 추가하지 않는다.

pop를 사용해서 explore의 원소를 제거하지 않으므로 explore에는 탐색한 모든 노드들이 저장된다.

그리고 탐색한 노드들과 그 노드들의 수를 반환하면 bfs함수의 작성은 완료된다.

 

# def solution(cards):
#     dict_cards = {i+1:v for i, v in enumerate(cards)}
#     group_1 = 0
#     group_2 = 0
    explored_node = []
    
    for i in range(1, len(cards)+1):
        if i not in explored_node:
            explored, number_node = bfs(dict_cards, i)
            explored_node.extend(explored)

 

다시 solution함수로 돌아온다.

이제 반복문을 사용해서 1번노드부터 순서대로 탐색을 한다. 이때 이미 탐색한 노드(explored_node에 추가된 노드)는 탐색하지 않는다.

bfs함수를 통해 함색한 노드는 explored에, 그리고 연결된 노드들의 갯수는 number_node에 각각 저장한다.

explored는 explored_node라는 리스트에 값들을 추가해준다. 이를 통해서 중복탐색을 방지할 수 있다.

 

# def solution(cards):
#     dict_cards = {i+1:v for i, v in enumerate(cards)}
#     group_1 = 0
#     group_2 = 0
#     explored_node = []
    
#     for i in range(1, len(cards)+1):
#         if i not in explored_node:
#             explored, number_node = bfs(dict_cards, i)
#             explored_node.extend(explored)
            if number_node >= group_2:
                group_2 = number_node
                if number_node >= group_1:
                    group_2 = group_1
                    group_1 = number_node
    
    return group_1 * group_2

 

이제 bfs함수를 통해 구한 노드의 수를 group_2와 비교해서 더 높은 값을 group_2에 새롭게 저장한다.

또한, group_1과도 비교후, 더 큰값을 저장하고 기존의 group_1의 값은 두번째로 큰 값이 되었으므로 group_2에 옮겨준다.

모든 그래프가 연결되어있을 경우 group_2의 값은 0이기때문에 문제의 조건에 부합한다.

 

이렇게 구해진 group_1과 group_2의 값을 서로 곱하면 최고점수의 기대값을 알 수 있다.

 

def bfs(graph, start):
    explore = [start]
    
    for node in explore:
        if graph[node] not in explore:
            explore.append(graph[node])
    return explore, len(explore)

def solution(cards):
    dict_cards = {i+1:v for i, v in enumerate(cards)}
    group_1 = 0
    group_2 = 0
    explored_node = []
    
    for i in range(1, len(cards)+1):
        if i not in explored_node:
            explored, number_node = bfs(dict_cards, i)
            explored_node.extend(explored)
            if number_node >= group_2:
                group_2 = number_node
                if number_node >= group_1:
                    group_2 = group_1
                    group_1 = number_node
    
    return group_1 * group_2

 

완료!