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

🌿 문제

2668번: 숫자고르기

 

 

🌿 해결 방법

directed graph에서 cycle의 개수와 cycle을 구성하는 노드를 찾는 문제이다.

이것도.... 한참 해보다가 결국 구글링을 하긴 했다....

dfs의 매개변수로 시작하는 노드와 현재노드를 전달한 후,

현재노드가 방문한적이 있으면서 현재 노드와 시작노드가 같은 경우 cycle이다.

 

따라서 이때 answer 배열에 현재 노드를 추가하면 된다!

현재노드를 방문한 적이 없다면 현재노드를 방문했다고 표시(visited[current]++;) 해주고 

다시 dfs를 돌려주면 된다.

 

그리고 가장 중요한 것은 26~28줄의 초기화...

이것 때문에 계속 틀렸다고 떴었다ㅎㅎ...

 

 

🌿 내 코드(C++)

// [2668] 숫자고르기
// https://www.acmicpc.net/problem/2668
// dfs
// cycle 개수 찾기!

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

void dfs(int, int);
int visited[102] = { 0 };
int a[102];
vector<int> answer;

int main(void)
{
    int n;
    scanf_s("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        scanf_s("%d", &a[i]);
    }
    
    for (int i = 1; i <= n; i++) {
        dfs(i, i);
        
        // ***initialization***
        for (int j = 1; j <= n; j++) 
            visited[j] = 0;
    }
    
    printf("%d\n", answer.size());
    for (int i = 0; i < answer.size(); i++) {
        printf("%d\n", answer[i]);
    }
}

void dfs(int start, int current)
{
    if (visited[current]) { 
    
    	// cycle인 경우
        if (current == start) { 
            answer.push_back(start);
        }
    }
    
    else {
        visited[current]++;
        dfs(start, a[current]);
    }
}