백준 2668 숫자고르기 (C++)

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector<int> ans;


void dfs(int cur, int s){


    if (visit[cur]) {
        if (s == cur) {
            ans.push_back(cur);
        }
        return;
    }

    visit[cur] = true;
    dfs(arr[cur], s);

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    cin >> n;

    arr.resize(n+1);


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

    for (int i = 1; i <= n; i++) {

        fill_n(visit, 101, false);
        dfs(i, i);


    }

    cout << ans.size() << "\n";
    for (const auto &item: ans) {
        cout << item << "\n";
    }

    return 0;
}

1. 문제

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

2. 풀이

사이클을 최대한 많이 모으는 문제이다. 예제를 살펴보자.

1	2	3	4	5	6	7
3	1	1	5	5	4	6

 

1행의 숫자->2행의 숫자를 연결한다. 이를 돌아서 처음 시작할 때의 자기 자신 노드로 돌아온다면, 사이클이 생성되었다 할 수 있다. 위의 경우 1->3->1의 사이클이 생성된다. 즉, 사이클이 생성된다면 1행의 숫자 집합과 2행의 숫자 집합이 일치하게 된다.

문제에서는 최대로 많이 뽑는 방법을 찾아야 한다. 5의 경우 자기 자신을 사이클로 가지게 되므로 이를 추가해준다. 

    bool visit[101];

    for (int i = 1; i <= n; i++) {

        fill_n(visit, 101, false);
        dfs(i, i);


    }

각 노드를 시작점으로 하여 dfs를 돌린다.

void dfs(int cur, int s){


    if (visit[cur]) {
        if (s == cur) {
            ans.push_back(cur);
        }
        return;
    }

    visit[cur] = true;
    dfs(arr[cur], s);

}

현재 위치를 visit에 표시해주고, 1행의 숫자->2행의 숫자를 통해 2행의 숫자를 방문한다. 계속 돌다가 처음의 위치로 돌아왔다면 이를 정답 배열에 추가해준다.

연산이 끝나고 정답 배열의 크기와 각 배열을 출력해주면 정답을 구할 수 있다.