백준)2668-숫자고르기

문제링크 : https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

문제

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1 이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

입력

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

풀이

결론부터 말하자면 시작한수가 다시 자기 자신이 돼야 만 정답이 될 수 있는 경우에 포함되는 사이클 문제이다. 이것과 비슷한 문제를 푼 적이 있는데 코드가 거의 99% 일치한다. 신기...

visit 배열 과 fin  배열을 선언해주었다. visit은 말 그대로 이 노드를 이미 방문한 적이 있다는 표기를 하기 위해 만들어 준 배열이다. fin 배열은 최초로 노드가 방문 시에 만 1로 초기화를 해주었다. 이렇게 해줌으로써 vistit으로 만 처리되고 fin 은 계속 0으로 유지되는 노드들이 존재한다. 이런 식으로 노드를 계속 다음 노드로 넘겨주다가 이미 방문 처리가 되어 있는 노드를  방문해야 할 차례가 올 것이다. 그때 fin이 '0' 이면 그 노드는 사이클이 존재하는 노드의 구성요소가 된다. 누군가가 자기를 선택한 저기 있다는 의미가 되기 때문이다.

핵심은 main 함수에 존재한다. main 함수에서 이미 방문된적이 있는 노드들은 dfs를 수행하지 않도록 해준다. 중복처리 방지를 위해서~^^!

 

#include<iostream>
#include<algorithm>
using namespace std;
 
 
int N;
 
int ans[101];
int fin[101];
int map[101];
int visited[101];
int cnt = 0 ;
 
void dfs(int n)
{
    int i;
 
    visited[n] = 1 ;
 
    if(visited[ map[n] ] == 0 )
    {
        dfs( map[n] );
 
    }
 
    else if( fin[map[n]] == 0)
    {
        ans[cnt++] = n;
        
        for( i = map[n] ; i !=n ; i = map[i] )
        ans[cnt++] = i;
 
 
    }
 
 
    fin[n] = 1;
 
 
 
}
 
 
 
 
int main()
{
    int i,j;
 
    cin >> N ;
 
    for(  i =1 ; i<= N ; i++)
        cin >>map[i];
 
 
 
 
    for(  i =1 ; i<= N ; i++)
    {
        if(visited[i]) continue;
        
            dfs(i);
 
    }
 
 
    sort(ans,ans+cnt);
 
    cout << cnt << "\n";
    for( i = 0 ;i<cnt; i++)
    cout << ans[i] << "\n"; 
 
 
    return 0;
}