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

문제링크 : https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[101];
int visited[101];
vector<int>result;

void dfs(int s, int e)
{
    if(visited[s])  //방문했다면
    {
        if(s == e)  //돌아옴
        {
            result.push_back(e);
        }
        else
        {
            return;
        }
    }
    else
    {
        visited[s] = 1; //방문처리
        dfs(arr[s], e); //이어서 탐색
    }
}

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

    int N;
    cin >> N;  

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

    for(int i=1; i<=N; i++)
    {
        memset(visited, 0 , sizeof(visited));
        dfs(i, i); //해당 값으로 돌아오는지 체크
    }

    cout << result.size() << "\n";
    for(int i=0; i<result.size(); i++)
    {
        cout << result[i] << "\n";
    }

    return 0;
}

조금 색다른 느낌의 dfs 문제이다.

현재 값을 시작으로 이어진 값(깊이)를 탐색하여 마지막에 다시 현재 값으로 돌아오는 지를 체크한다.

방문 배열을 이용하여 체크해주며, 만약 방문된 값을 다시 방문했다면 이는 돌아왔거나, 이후 탐색을 해도 무의미한 사이클을 도는 것이다.

 

무사히 돌아왔으면 결과값에 담아주고, 아니라면 재귀를 종료한다.