프로그래머스 혼자 놀기의 달인 c++

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> result;
bool c[101] = {false,};

bool cmp(int a,int b) {
    return a > b;
}

void bfs(vector<int> cards,int index) {
    queue<int> q;
    bool check[101] = {false,};
    
    q.push(cards[index]-1);
    check[index] = true;
    c[index] = true;
    int cnt = 1;
    
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        if(check[x]) break;
        
        check[x] = true;
        c[x] = true;
        
        q.push(cards[x]-1);
        cnt++;
    }
    result.push_back(cnt);
}

int solution(vector<int> cards) {
    int answer = 0;
    for(int i=0; i<cards.size(); i++) {
        if(!c[i]) {bfs(cards,i);}
    }
    
    sort(result.begin(),result.end(),cmp);
    
    if(result.size() == 1) { answer = 0; }
    else {answer = result[0] * result[1]; }
    
    return answer;
}

**

union find 를 생각하면 된다

결국 연결된 숫자들은 아무거나 선택해도 연결되기 때문

**

 

프로그램 흐름도

1. 카드의 개수만큼 합집합을 찾는 과정을 반복

2. 합집합의 원소 개수를 result 벡터에 저장

3. result 벡터 내림차순으로 정렬

4. result 벡터의 원소가 하나일때는 모두 연결된 것이므로 answer 에 0 저장 , 두개 이상일 경우 0번,1번 인덱스 곱