[C++][프로그래머스] 혼자 놀기의 달인(Union-Find) 🔥

프로그래머스

 

📄 문제

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

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

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

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

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

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

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

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

 

📝 풀이

#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

vector<int> arr;

// Find
int Find(int n)
{
    if (n == arr[n]) return n; // n번째 그룹에 바로 속해있는경우 리턴
    else return arr[n] = Find(arr[n]); // n번째 그룹에 바로 속하지 않은경우, DFS로 실제 속한 그룹을 찾기
}

// Union
void Union(int a, int b)
{
    a = Find(a); // a가 속한 실제 그룹 찾기
    b = Find(b); // b가 속한 실제 그룹 찾기

    // 서로 다른 그룹이라면?
    if (a != b)
        arr[a] = b; // arr[a]는 이제부터 b그룹에 속함
}

int solution(vector<int> cards) {
    
    arr = vector<int>(cards.size() + 1);
    
    // 집합 정보 초기화
    for (int i = 1; i <= cards.size(); ++i)
        arr[i] = i;
    
    // 각 인덱스에서 가리키는 cards[i]번째 인덱스를 같은 그룹으로 묶기
    for(int i = 0; i < cards.size(); ++i)
        Union(i + 1, cards[i]);
    
    // 동일한 그룹끼리 값을 동일하게 검사
    for(int i = 1; i <= cards.size(); ++i)
        Find(i);
    
    // 그룹의 크기를 구하기 위해 map에 저장
    map<int, int> m;
    for(int i = 1; i <= cards.size(); ++i)
        ++m[arr[i]];
    
    // 우선순위 큐를 이용하여 내림차순 정렬
    priority_queue<int> q;
    for(pair<int, int> p : m)
        q.push(p.second);
    
    // 그룹의 사이즈가 1이라면 0 리턴
    if(q.size() == 1)
        return 0;
    
    // 그룹의 사이즈가 2이상이라면, 2개를 가져와 곱하여 리턴
    int answer = 1;
    for(int i = 0; i < 2; ++i)
    {
        answer *= q.top();
        q.pop();
    }
    
    return answer;
}

• Union-Find 알고리즘을 이용하여 주어진 배열에 대한 그룹을 정리합니다.
• 그 후에 map을 이용하여 그룹에 속한 요소의 개수를 구한 후 우선순위 큐를 이용하여 가장 큰 값 두개를 곱하여 리턴합니다.

 

⭐️ Union-Find 구현

#include <iostream>
#include <vector>
using namespace std;

vector<int> arr;

// n이 속한 그룹의 번호를 리턴
int Find(int n) {
    if(arr[n] == n) return n;
    else return arr[n] = Find(arr[n]);
}

// a와 b가 같은 그룹이 되도록 결합
void Union(int a, int b) {
    arr[Find(a)] = Find(b);
}

// 각 요소가 실제로 속한 그룹을 가리키도록 갱신
void Refresh()
{
    for(int i = 0; i < arr.size(); ++i)
        Find(i);
}

int main(int argc, const char * argv[]) {
    
    // 각 원소가 가리키는곳은 같은 그룹으로 결합(0번째 원소인 1은 0과 같은 그룹)
    vector<int> v = vector<int>{1, 5, 0, 4, 3, 2};
    arr = vector<int>(v.size());
    
    // 각 번호에 맞는 그룹으로 초기화
    for(int i = 0; i < v.size(); ++i)
        arr[i] = i;
    
    for(int i = 0; i < v.size(); ++i)
    {
        Union(v[i], i);
        for(int j = 0; j < v.size(); ++j)
            printf("%d ", arr[j]);
        printf("\n");
    }
    
    printf("갱신 후\n");
    Refresh();
    
    for(int j = 0; j < v.size(); ++j)
        printf("%d ", arr[j]);
    printf("\n");
    
    return 0;
}