백준 C++ 숫자고르기 골5 문제 풀이

 

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

 

이 글을 읽는다면 문제는 이미 다 알고 있다고 생각합니다.

구해야하는 정답은 첫 번째 줄에서 뽑은 수와  두 번째에서 뽑은 수가 같은 집합의 최대 크기이다.

두번째 줄에서 주어진 수에서 인덱스번호가 없는 2와 7은 첫번째 줄에서 선택할 필요가 없다.
-> 왜냐하면 2와 7을 뽑아봤자 2번째 줄에 2와 7이 없기 때문에 같은 수를 뽑을 수가 없기 때문이다.

일단 이해하기 쉽도록 그래프를 그려줍니다.
-> 그래프를 그릴 때 각 노드들은 인덱스 번호이며 연결되어있는 값들은 2번째 줄에서 준 값들의 인덱스 번호입니다.

그럼으로 2와 7을 기준으로  각 노드들에 연결되어 있는 2와 7를 제거합니다.

## 먼저 2를 제거합니다

2가 연결된 곳은 1 번 노드였고 1번 노드에 자식 노드가 있음으로 제거할 대상이 아닙니다. 이후 2가 연결된 곳이 없음으로 7를 제거합니다.

## 7 제거

7이 연결된 곳은 6이었고, 지우니, 자식 노드가 없습니다. 이로 인해 6도 사용하지 못합니다. 그럼으로 6도 지워줍니다.

## 6 제거

6이 연결된 곳은 4였고 지우니, 자식 노드가 없으므로 쓰지 못합니다.

## 4 제거

4가 연결된 곳은 5였고 제거하니 자식 노드가 남아있음으로 제거를 멈춥니다.

다 제거하고 나니  사용가능한 수는 총 3개입니다.

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

int inputs[101];
vector<int> adj[101];

int main() {
    int n;
    cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> inputs[i];
        adj[inputs[i]].push_back(i);
    }

    int answer = n;
    for(int i=1; i<=n; i++) {
        if(adj[i].size() == 0) {
            
            int k = i;
            int index = inputs[i];
            
            while(true) {
                // 제거
                for(int j=0; j<adj[index].size(); j++) {
                    if(adj[index][j] == k) {
                        adj[index].erase(adj[index].begin()+ j);
                        answer--;
                        break;
                    }
                }
                
                if(adj[index].size() == 0) {
                    k = index;
                    index = inputs[index];
                    
                } else {
                    break;
                }
            }
        }
    }

    vector<int> answers;
    for(int i=1; i<=n; i++) {
        if(adj[i].size() != 0 ) {
            for(int j=0; j<adj[i].size(); j++) {
                answers.push_back(adj[i][j]);
            }
        }
    }
    sort(answers.begin(), answers.end());

    cout << answer << "\n";
    for(int i=0; i<answers.size(); i++){
        cout << answers[i] << "\n";
    }
}

## 재귀로 작성

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

int inputs[101];
vector<int> adj[101];
int answer;
int n;

void remove(vector<int>& temp, int target){
    for(int j=0; j<temp.size(); j++) {
        if(temp[j] == target) {
            temp.erase(temp.begin()+ j);
            answer--;
            break;
        }
    }
}

void recrucive(int target, int index) {
    
    remove(adj[index], target);
            
    if(adj[index].size() == 0) {
        recrucive(index, inputs[index]);
    } else {
        return;
    }

}

int main() {
    cin >> n;
    answer = n;
    for(int i=1; i<=n; i++) {
        cin >> inputs[i];
        adj[inputs[i]].push_back(i);
    }

    for(int i=1; i<=n; i++) {
        if(adj[i].size() == 0) {
            recrucive(i, inputs[i]);
        }
    }

    vector<int> answers;
    for(int i=1; i<=n; i++) {
        if(adj[i].size() != 0 ) {
            for(int j=0; j<adj[i].size(); j++) {
                answers.push_back(adj[i][j]);
            }
        }
    }
    sort(answers.begin(), answers.end());

    cout << answer << "\n";
    for(int i=0; i<answers.size(); i++){
        cout << answers[i] << "\n";
    }
}