백준 2668번 숫자고르기

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

DFS(Depth First Search)를 통해 사이클을 이루는 노드들을 찾는 문제였습니다.

알고리즘은 아래와 같습니다.

1. DFS 함수의 매개변수로 탐색을 시작하는 노드와 움직인 노드를 전달합니다.

2. 사이클을 이루면 cycle 배열에 저장하고 노드의 갯수를 증가시킵니다.

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 100 + 1;

 

int N;

int cnt;

 

int node[MAX];

bool visited[MAX];

bool cycle[MAX];

 

bool DFS(int startNum, int nodeNum)

{

        if (visited[nodeNum])

                 return false;

 

        visited[nodeNum] = true;

 

        //사이클을 이루면

        if (startNum == nodeNum || DFS(startNum, node[nodeNum]))

        {

                 cnt++;

                 cycle[nodeNum] = true;

                 return true;

        }

        return false;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 1; i <= N; i++)

                 cin >> node[i];

 

        for (int i = 1; i <= N; i++)

        {

                 for (int j = 1; j <= N; j++)

                         visited[j] = cycle[j]; //이미 사이클을 이루는 집합은 재방문 X

                 DFS(i, node[i]);

        }

       

        cout << cnt << endl;

        for (int i = 1; i <= N; i++)

                 if (cycle[i]) //사이클 이루는 노드들 출력

                         cout << i << " ";

        cout << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~