[Programmers] 혼자 놀기의 달인

혼자 놀기의 달인

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

풀이

1. BFS을 이용하여 연결된 상자 그룹을 구한다.
2. 최고 점수를 얻기 위해 모든 상자 그룹을 가진 vector을 size()를 기준으로 내림차순 정렬한다.
3. 그 중 첫번째 원소와 두번째 원소의 곱이 리턴

예외) 모든 상자 그룹이 하나일 수 있음.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool visited[101];
vector<vector<int>> groups;

vector<int> BFS(vector<int> cards, int i){ // i: 상자 번호
    visited[i] = 1;
    vector<int> group;    
    group.push_back(i);
    int n = cards[i]; // n: 카드 번호

    while(!visited[n]){
        visited[n] = 1;
        group.push_back(n);
        n = cards[n];
    }
    return group;
}

int solution(vector<int> cards) {
    cards.insert(cards.begin(),0);
    int N = cards.size();
    for(int i=1; i<N; i++)
        if(!visited[i])
            groups.push_back(BFS(cards, i));

    if(groups.size()==1) return 0;
    sort(groups.begin(), groups.end(), 
         [](vector<int> &v1, vector<int> &v2){
            return v1.size() > v2.size();
    }); // lambda
    return groups[0].size()*groups[1].size();
}

정리