[백준] 2668: 숫자고르기

0. 문제 주소

 

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

2668번: 숫자고르기

 

 

1. 풀이

 

[PS] - [BOJ] 9466: 텀 프로젝트 랑 똑같은 문제.

 

윗줄에서 적절히 숫자들을 골랐을 때, 고른 숫자들에 대응되는 밑줄의 숫자들의 집합이 "윗줄에서 고른 숫자들의 집합"과 일치해야 한다.

 

정답이 1, 3, 5를 골랐을 때인데, 다음과 같이 생각하면 해답이 쉽게 떠오른다.

1. 윗줄에서 1을 고른다 -> 대응되는 밑줄의 숫자는 3이다.
2. 이번엔 1.에서 나온 밑줄의 숫자 3을 윗줄에서 고른다 -> 대응되는 밑줄의 숫자는 1이다.
3. 1은 이미 골랐던 숫자이다 : 사이클의 형태

[PS] - [BOJ] 9466: 텀 프로젝트 과 유사하다고 한 이유는, 모든 정점의 outdegree가 1인 그래프에서 사이클에 속한 정점의 개수를 찾는 상황이 정확히 똑같기 때문이다. 다만 9466번에선 개수만 구해야 했다면, 이 문제에선 그 사이클에 속한 정점 번호까지 요구하는 것이 다른 점이다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define MAX 105

using namespace std;

int N;
int E[MAX];
bool visited[MAX];
bool finished[MAX];
vector<int> ans;

void DFS(int curr){
    visited[curr] = true;
    int next = E[curr];
    if (visited[next]){
        if (!finished[next]){
            for (int start = next; start != curr; start = E[start]) {
                ans.push_back(start);
            }
            ans.push_back(curr);
        }
    }
    else DFS(next);

    finished[curr] = true;

}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &N);
    for (int i=1;i<=N;i++){
        scanf("%d", &E[i]);
    }
    for (int i=1;i<=N;i++){
        if (!visited[i]) DFS(i);
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for (int n: ans){
        printf("%d\n", n);
    }
}