[BOJ/C++] 숫자고르기(2668번)

1. 개요

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

2668번: 숫자고르기

1-1. 설명

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

1-2. 제한 사항

 - 첫 줄에는 N을 나타내는 정수가 주어지며, 1 이상 100 이하 자연수

 - 다음 줄부터 표의 둘째줄에 들어가는 정수들이 순서대로 한줄에 하나씩 입력

---

2. 구현

2-1. 풀이

어떤 풀이로 풀어야할지 감이 안와 다른 사람들의 풀이를 참조했다. DFS 방식으로, 1부터 N까지 하나씩 DFS를 돌려 다음 인덱스를 찾아가 마지막 인덱스가 처음 인덱스와 동일하면 결과 변수에 넣는 방식으로 진행했다. 풀이를 알아내니, 구현 자체는 그리 어렵지 않았다. 

2-2. 코드

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int nums[100], N, start;
bool check[100];
set<int> result;

void DFS(int index);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 1; i <= N; i++) cin >> nums[i];

    for (int i = 1; i <= N; i++) {
        start = i;
        DFS(i);
    }

    cout << result.size() << "\n";
    for (auto iter = result.begin(); iter != result.end(); iter++) {
        cout << *iter << "\n";
    }
    return 0;
}

void DFS(int index) {
    check[index] = true;
    int nextIdx = nums[index];
    if (start == nextIdx) result.insert(start);
    if (!check[nextIdx]) DFS(nextIdx);

    check[index] = false;
}