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

 

빨간색 원으로 쳐진 부분을 고르면, 윗줄(1, 3, 5) 아랫줄(3, 1, 5)로 동일한 집합이 된다.

초록색 원으로 쳐진 부분을 고르면, 윗줄(2, 4) 아랫줄 (1, 5)가 되어 서로 다른 집합이 된다.

 

이런식으로, 윗줄과 아랫줄의 숫자 집합이 동일하게 되도록 인덱스를 선택하면 되는 문제이다.

물론, 그런 경우가 하나의 문제에서 여러 경우가 나올 수 있기 때문에 집합의 크기가 최대가 되는 경우를 출력하면 된다.

 

문제 풀이

 

해당 문제는 순환하는 숫자 집합을 모두 구하면 되는 문제이다.

본인은 DFS를 활용하여 순환하는 숫자 집합을 구하였다.

 

순환하는 숫자 집합이란, 아래와 같다.

빨간색 화살표는 서로 순환하고 잇는 상태이고, 하늘색 화살표는 순환하지 않는 상태이다.

 

1번 인덱스로부터 시작해보자.

가리키고 있는 3번 인덱스로 가보면, 3번 인덱스는 다시 1번 인덱스를 가리키고 있다.

 

즉, 1과 3은 서로 순환하는 상태이다.

 

반면, 2의 경우엔 1을 가리키고 있지만, 1 -> 3 -> 1 -> 3 무한히 반복하며, 2로 다시 돌아오지 않는다.

즉, 2는 순환 집합에 포함되지 않는 것이다.

 

4,6,7도 마찬가지이다. 화살표를 따라 움직여도 본인으로 돌아오지 않기 때문에 순환 숫자 집합에 포함되지 않는다.

5의 경우는 본인을 상대로 무한히 반복하고 있다. 이것 또한 순환하고 있다고 표현할 수 있다.

 

그러므로, 이 문제의 답은 순환하는 숫자 집합을 모두 합친 {1, 3, 5}가 답이 된다.

 

그런데, 순환하고 있는 것을 어떻게 코드로 판별할까?

본인은 DFS를 활용하여 구하였다.

 

만약, 값을 계속 타고가서 본인에게 다시 돌아올 수 있다면 그 과정에서 지나온 숫자는 모두 순환 집합에 있다고 표현할 수 있다.

 

위 그림과 같이, 개수만큼 방문체크 배열을 만들어주었다.

하나씩 타고가보자.

이렇게, 1번 인덱스에 방문체크를 해주었다.

다음은 3번으로 가보자.

이렇게, 3번 인덱스를 가보았더니 3번 인덱스의 값이 DFS를 처음 시작한 인덱스(1)과 동일하였다.

즉, 시작 인덱스부터현재 인덱스까지 순환하고 있음을 알 수 있다.

 

이 때, 방문체크가 되어있는 인덱스를 정답 배열에 넣어주자.

정답배열 : (1, 3)

 

다시, 2번 인덱스부터 DFS를 시작해보자.

이렇게 출발하여, 끝까지 가보자.

이 상황에서 초록색 화살표를 보자.

1번 인덱스로 다시 이동해야 하지만, 1번 인덱스가 방문체크가 되어있어 이동할 수가 없다.

즉, 이 DFS는 여기서 종료되는 것이다.

 

이렇게 DFS가 방문체크 배열에 의해 이동이 막히기 전에, 시작 인덱스를 만나지 못한다면 해당 시작 인덱스는 순환 숫자 집합에 포함되지 않는다고 할 수 있다.

 

이렇게, 모든 숫자에 대해 검색하여 순환하는 숫자들을 집합에 넣어주면 끝이다.

 

풀이 코드

 

int NumSize = 0;
std::cin >> NumSize;

std::vector<int> Nums(NumSize + 1, 0);
for (int i = 1; i <= NumSize; i++)
{
    std::cin >> Nums[i];
}

std::vector<bool> isVisit(NumSize + 1, false);

 

입력을 모두 받아준 뒤, 저장해주자.

이후, 방문체크를 담당할 배열을 하나 선언해주자.

 

아래는 DFS코드이다.

std::set<int> AnswerSet;

void DFS(std::vector<int>& _Nums, std::vector<bool>& _isVisit, int _StartIndex, int _CurIndex)
{
    _isVisit[_CurIndex] = true;

    if (_Nums[_CurIndex] == _StartIndex)
    {
        AnswerSet.insert(_StartIndex);
        _isVisit[_CurIndex] = false;
        return;
    }

    int NextIndex = _Nums[_CurIndex];

    if (_isVisit[NextIndex] != true)
    {
        DFS(_Nums, _isVisit, _StartIndex, NextIndex);
    }

    _isVisit[_CurIndex] = false;
}

 

인자로는 숫자 배열, 방문체크 배열, 시작 인덱스, 현재 인덱스를 받아주고 있다.

 

먼저, 함수에 진입하게 되면 현재 인덱스에 대한 방문체크를 진행해주었다.

이후, 현재 인덱스가 가리키는 값이 시작 인덱스와 같다면 시작 인덱스를 순환하는 집합에 포함된다고 판단하여, AnswerSet에 저장해주었다.

 

정답은 Set에 넣지 않고 vector같은 다른 자료구조에 넣어도 된다. 본인은 정렬을 확실하게 하기 위해 Set을 사용하였지만, Set을 사용하지 않아도 된다.

 

이후, 다음 인덱스를 구해준 뒤, 다음 인덱스에 대한 방문체크가 되어있지 않다면 DFS를 계속 진행해주었고 방문체크가 되어있다면 여기서 DFS를 끝내도록 하였다.

 

함수가 끝나는 순간 방문체크를 해제해주었다.

 

아래는 Main함수의 남은 부분이다.

for (int i = 1; i <= NumSize; i++)
{
    DFS(Nums, isVisit, i, i);
}

std::set<int>::iterator StartIter = AnswerSet.begin();
std::set<int>::iterator EndIter = AnswerSet.end();

std::cout << AnswerSet.size() << "\n";

while (StartIter != EndIter)
{
    std::cout << *StartIter << "\n";
    StartIter++;
}

return 0;

 

DFS를 인덱스만큼 돌려주었다.

이후, AnswerSet의 size와 AnswerSet의 원소들을 차례대로 출력해주면 문제는 해결된다.

 

코드 전문

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

std::set<int> AnswerSet;

void DFS(std::vector<int>& _Nums, std::vector<bool>& _isVisit, int _StartIndex, int _CurIndex)
{
    _isVisit[_CurIndex] = true;

    if (_Nums[_CurIndex] == _StartIndex)
    {
        AnswerSet.insert(_StartIndex);
        _isVisit[_CurIndex] = false;
        return;
    }

    int NextIndex = _Nums[_CurIndex];

    if (_isVisit[NextIndex] != true)
    {
        DFS(_Nums, _isVisit, _StartIndex, NextIndex);
    }

    _isVisit[_CurIndex] = false;
}

int main()
{
    Init();

    int NumSize = 0;
    std::cin >> NumSize;

    std::vector<int> Nums(NumSize + 1, 0);
    for (int i = 1; i <= NumSize; i++)
    {
        std::cin >> Nums[i];
    }

    std::vector<bool> isVisit(NumSize + 1, false);

    for (int i = 1; i <= NumSize; i++)
    {
        DFS(Nums, isVisit, i, i);
    }

    std::set<int>::iterator StartIter = AnswerSet.begin();
    std::set<int>::iterator EndIter = AnswerSet.end();

    std::cout << AnswerSet.size() << "\n";

    while (StartIter != EndIter)
    {
        std::cout << *StartIter << "\n";
        StartIter++;
    }

    return 0;
}