[프로그래머스] 혼자 놀기의 달인 C++ 풀이 및 해설

 

https://school.programmers.co.kr/learn/courses/30/lessons/131130#qna

프로그래머스

 

풀이 방법

bool 배열로 각 상자의 방문 여부를 관리한다.

1. 반복문으로 모든 상자를 돌며 방문 여부를 확인한다.
2. 방문하지 않은 상자라면 방문하여 타고타고 들어가 연결된 모든 상자를 방문한다.
3. 타고타고 들어가 방문한 상자의 개수를 vector<int> 변수에 넣어준다.
4. 모든 상자를 방문하면 vector<int>를 내림차순으로 정렬한다.
5. 0번째 1번째 원소의 곱을 정답으로 쓴다.
   1. 주의! 한번에 모든 상자를 방문하여 2번 그룹이 안생길 수 있으니 vector<int>의 크기를 확인해주자.

 

간단하다~

 

전체 코드

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

using namespace std;

int DFS(int idx, bool visit[], vector<int> &cards) {
    
    int sum = 1;
    while(!visit[cards[idx]-1]) {
        idx = cards[idx]-1;
        visit[idx] = true;
        sum += 1;
    }

    return sum;
}


int solution(vector<int> cards) {
    int answer = 0;
    
    bool visit[101]; // 각 위치의 상자 방문 여부
    vector<int> v; // 각 그룹의 상자 개수를 담을 vector
    fill(&visit[0], &visit[101], false);
    
    for(int i=0; i<cards.size(); i++) {
        if(!visit[i]) {
            visit[i] = true;
            int result = DFS(i, visit, cards); // 연결된 모든 상자 방문
            v.push_back(result); // 모든 상가 방문한 개수(result)를 추가
        }
    }
    
    // 내림차순 정렬
    sort(v.begin(), v.end(), greater<>());
    
    // 한번에 모든 상자를 돌아버릴 수 있으니 2번 그룹 존재하는지 확인해줘야함.
    if(v.size()>=2) {
        answer = v[0] * v[1]; // 가장 큰 상자개수 2개를 곱함.
    }
    
    return answer;
}