[개쉬운 풀이] 백준 2668 숫자고르기

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

문제

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

 

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

 

생각

: 뽑힌 정수들이 이루는 집합과 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치하려면 처음 시작한 idx를 돌아와 마지막 arr[idx] == idx로 돌아와 Loop를 이루어야한다.

 

풀이

1. DFS를 재귀함수로 구현을 할 때, 언제 멈추어야하는지 먼저 생각한다.

2. 방문을 했던 노드나, 이미 루프가 형성된 노드면 return한다.

3. 각 번호를 모두 루프가 형성되는지 재귀함수에 넣어본다.

4. 결과값을 형식에 맞게 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
#define endl '\n'
using namespace std;

const int MAX = 101;

int n;
int arr[MAX];
bool isLoop[MAX];
bool isVisited[MAX];

/*
뽑힌 정수들이 이루는 집합과 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치하려면

idx와 arr[idx] 값들의 집합이 일치해야한다.
즉, idx로 시작해서 arr[idx2] == idx로 도착하는 loop를 찾아야한다.
 

*/

void init(){
    memset(isLoop, 0, sizeof(isLoop));
    memset(arr, 0, sizeof(arr));
    memset(isVisited, 0, sizeof(isVisited));
}

void input(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
}

//재귀함수를 구현할 때 각 회차를 기준으로 구현한다. 
//그리고 변하는 값들과 변해서는 안되는 값들을 고민한다.
void findLoop(int idx, int target){
	//해당 숫자가 이미 루프를 형성했으면 탐지하지 않는다.
    if(isLoop[idx]) return;
    if(isVisited[idx]){
        //is Loop!
        if(idx == target){
            for(int i = 0; i < MAX; i++){
                if(isVisited[i]){
                    isLoop[i] = true;
                }
            }
        }
        //무한루프 방지
        return;
    }
    else{
        isVisited[idx] = true;
        int nextIdx = arr[idx];
        findLoop(nextIdx, target);
    }

}

void sol(){
    for(int i = 1; i <= n; i++){
    	// ** 각 회차의 isVisited를 초기화 해준다. **
        memset(isVisited, 0, sizeof(isVisited));
        findLoop(i,i);
    }
    
    vector<int> v;
    int answer = 0;
    //isLoop를 출력하기 위해 담는다.
    for(int i = 1; i <= n; i++){
        if(isLoop[i]) v.push_back(i);
    }

    cout << v.size() << endl;
    for(int x : v){
        cout << x << endl;
    }
}



int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    init();
    input();
    sol();

    return 0;
}