[백준, C++] 2668 - 숫자 고르기

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

2668번: 숫자고르기

 

문제 분석

N개의 숫자들이 주어진다. 이를 1-base index 배열에 매칭시켜보면, 이런 구조이다.

index	1	2	3	4	5	6	7
arr[index]	3	1	1	5	5	4	6

여기서, index들을 적절히 뽑으면 index 집합과 arr[index] 집합이 일치하게 될 수 있다. 이 경우에는 index 집합으로 [1, 3]을 만들거나, [1, 3, 5]를 만들면 arr[index] 집합이 [1, 3], [1, 3, 5]로 일치하게 된다.

 

이처럼 index 집합과 arr[index] 집합이 일치하도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾아내야 한다.

 

처음에는 이게 무슨 문제인가 싶다가, 이 배열을 그래프로 바꿔 생각해봤다. 그렇다면 위 배열을 그래프로 어떻게 바꿀 수 있을까 ? 나는 단방향 그래프를 생각했다. index = 1, arr[index] = 3이 의미하는 것은 1에서 3으로 가는 경로가 있음을 의미한다. 흔히 그래프 탐색 문제를 보면, 이런 입력들이 주어지지 않는가 ?

 

M개의 줄에 걸쳐 출발지 u, 도착지 v가 주어진다. 이는 u에서 v로 가는 경로가 존재한다는 것을 의미한다.

 

여기서는 index가 u, 즉 출발지에 해당하고 arr[index]가 v, 즉 도착지에 해당하는 개념으로 바꾸는 것이다. 그럼 문제에서 말하는 index 집합과 arr[index] 집합이 일치한다는 전제 조건은 어떻게 이해해야 할까 ? 이는 사이클의 개념으로 생각했다.

 

index 집합으로 [1, 3]을 생각해보자. index = 1, arr[index] = 3이므로 1에서 3으로 가는 경로가 있음을 의미한다. 그럼 1에서 출발해 3에 도착할 수 있다. 3에 도착하면 이번에는 3이 출발지가 된다. index = 3, arr[index] = 1이므로, 3에서 출발해 다시 1로 되돌아올 수 있다. 이처럼 최초 출발지에서 출발해서, 다시 최초 출발지로 되돌아오면 index 집합과 arr[index] 집합이 일치한다는 의미가 된다.

 

그래서 나는 BFS 개념을 살짝 응용해 각 index들을 최초 출발지로 정하고, BFS를 수행하면서 다시 최초 출발지로 되돌아올 수 있는지를 체크하면 될 것이라 생각했다. 이 과정에서 중복이 발생하지 않도록 결과를 담기 위해 자료구조 set을 사용하면 되겠다고 생각했다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int n;
int arr[101];
set<int> result;

void getInput();
void solve();
void printResult();

void checkCycle(int);

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

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

void checkCycle(int start) {
    queue<int> q;
    set<int> tempResult;
    bool visited[101] = {false};
    bool isCycle = false;

    q.push(start);
    visited[start] = true;
    tempResult.insert(start);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        int next = arr[cur];

        if (next == start) {
            isCycle = true;
        }

        if (!visited[next]) {
            q.push(next);
            visited[next] = true;
            tempResult.insert(next);
        }
    }

    if (isCycle) {
        for (auto i : tempResult) {
            result.insert(i);
        }
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        checkCycle(i);
    }
}

void printResult() {
    cout << result.size() << "\n";
    for (int i : result) {
        cout << i << "\n";
    }
}

 

코드 설명

조금 투박하지만 2개의 set을 사용했다. 하나는 각각의 BFS 탐색 과정에서 거쳐온 정점 번호를 저장하기 위한 임시 result이고, 하나는 최종적으로 사이클이 생기는 경로에 있는 정점을 담을 result set이다. 그리고 checkCycle() 메서드의 파라미터로 최초 출발지를 전달함으로써 BFS 과정에서 최초 출발지로 다시 가게 될 수 있는지를 체크할 수 있도록 했다.

 

풀이를 생각하고 나서 구현하는 것이 까다로운 편은 아니었으나, 배열을 보고 그래프를 만들어 사이클이 존재하는지를 확인하면 되겠다는 문제 해결 방식을 떠올리는 것이 까다로운 문제였다. 골드 ... 값어치 하는 듯 ?