백준 2668번 숫자고르기 - C++ 풀이

---

 

1. 첫째 줄에서 둘째 줄로 가는 간선을 추가한다.
2. 완성된 그래프에서 사이클에 속하는 숫자들을 선택한다.

 

1. 첫째 줄에서 둘째 줄로 가는 간선을 추가한다.

 문제에 주어진 예시 상황에서 첫째 줄의 1을 선택했다고 가정하자. 이에 대응하는 둘째 줄 숫자는 3이므로 첫째줄에서도 3을 추가해야 한다. 따라서 첫째 줄의 3을 고르고 나면, 또 첫째 줄 3에 대응하는 둘째 줄 숫자는 1이므로 첫째줄에서 1을 골라야 한다.
 이러한 흐름을 그래프로 나타낼 수 있다. 각 숫자를 정점이라고 생각하고, 첫째 줄에서 둘째 줄로 가는 간선을 추가하여 두 집합이 일치하기 위해 추가해야 하는 수의 흐름을 나타낸다. 문제에서 주어진 예시 상황의 경우 1 -> 3, 2 -> 1, 3 -> 1,... 을 추가하면 된다.

 

2. 완성된 그래프에서 사이클에 속하는 숫자들을 선택한다.

 계속해서 간선을 따라 가며 필요한 숫자들을 추가하다가, 이미 방문했던 정점에 재방문하게 되면(사이클이 생성되면) 두 집합이 일치한 것이다. 모든 정점에 대해 DFS를 진행해서 해당 정점이 사이클에 속한다면 해당 숫자를 고르면 된다.

 

반응형

---

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int N;
int arr[101];
bool visit[101];
vector<int> ans;

void DFS(int curr, int start) {
    if (visit[curr]) {
        if (start == curr) ans.push_back(curr);
        return;
    }
    
    visit[curr] = true;
    DFS(arr[curr], start);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    for (int i=1; i<=N; i++) cin >> arr[i];
    
    // 사이클에 속한 노드들을 전부 선택
    for (int i=1; i<=N; i++) {
        memset(visit, 0, sizeof(visit));
        DFS(i, i);
    }
    
    cout << ans.size() << "\n";
    for (auto x: ans) cout << x << "\n";

    return 0;
}