Programmers Level 2 :: 혼자 놀기의 달인

문제의 핵심은 상자의 묶음을 찾는 것이고, 이중 가장 큰 2개의 상자 묶음을 찾아 최댓값을 구해야 합니다.
상자의 개수가 100개이기 때문에 만들어질 수 있는 모든 상자 묶음을 찾아도 효율성 측면에서 문제가 되질 않습니다.

따라서 모든 상자의 묶음을 찾아주면 됩니다. 저는 상자 A -> 상자 B로 계속 이동하는 재귀 문을 작성해서 상자의 묶음을 찾았습니다.
한 가지 주의사항이 있는데요, 바로 전체 상자 묶음이 1개인 경우 점수가 0이라는 점입니다. 예를 들어 1, 2, 3, 4, 5, 6, 7과 같이 상자가 배치된 경우에 말이죠

이 부분은 아주 간단하게 처리할 수 있습니다. 모든 상자 묶음의 개수를 구할때마다 벡터에 넣고, 마지막으로 이 벡터에 0을 넣어줍니다.
벡터를 내림차순으로 정렬합니다. 그리고 우리가 찾고 싶은 값은 최댓값이므로 벡터의 0, 1번째 인덱스 값들을 꺼내 곱해주면 최댓값도 보장하고 0도 바로 출력할 수 있습니다.

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> v;
bool visited[110];

int dfs(int card, vector<int>& cards) {
    int temp = 1;
    int next = cards[card-1];
    if(!visited[next]) {
        visited[next] = true;
        temp += dfs(next, cards);
    }
    return temp;
}

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

int solution(vector<int> cards) {
    memset(visited, false, sizeof(visited));
    
    for(auto card : cards) {
        if(visited[card]) continue;
        visited[card] = true;
        int result = dfs(card, cards);
        v.push_back(result);
    }
    v.push_back(0);
    sort(v.begin(), v.end(), compare);
    
    return v[0] * v[1];
}