[C++] Programmers | 혼자 놀기의 달인

혼자 놀기의 달인

프로그래머스

---

✍🏻 풀이

문제의 조건을 만족하도록 카드를 뽑다 보면 반드시 사이클(cycle)이 생기게 되어있다.

우리는 주어진 카드에서 사이클을 모두 순회하고, 카드를 가장 많이 선택하는 사이클 두 개를 선택하여 곱한 값을 return하면 된다.

 

사이클을 돌기 위해 DFS를 사용하였고, 카드를 선택할 때마다 sum 값을 1 증가하여 뽑은 카드의 개수를 저장해 주었다.

이렇게 한 사이클을 돌면 나오는 카드의 개수인 sum을 벡터에 저장하고 sort를 하여 답을 도출해 냈다.

 

이때, 벡터의 크기가 1이면 사이클이 하나밖에 없으므로 점수는 0이 된다.

---

✅ Accept Code

// programmers week5-4
// 혼자 놀기의 달인

#include <bits/stdc++.h>

using namespace std;

int DFS(vector<int> &cards, int idx, int sum) {
    if (cards[idx] == 0) return sum;
    int cur = cards[idx];
    cards[idx] = 0;
    return DFS(cards, cur - 1, sum + 1);
}

int solution(vector<int> cards) {
    vector<int> answer;
    for (int i = 0; i < cards.size(); i++) {
        if (cards[i] == 0) continue;
        int cnt = DFS(cards, i, 0);
        answer.push_back(cnt);
    }
    sort(answer.rbegin(), answer.rend());
    if (answer.size() == 1) return 0;
    else return answer[0] * answer[1];

}