백준 숫자고르기 C++

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

2668번: 숫자고르기

---

그래프에서 사이클이 발생한다면, 정수를 뽑을 수 있습니다.

만약 n이 3이고, 입력이 {3,1,2}가 주어진다면, 그래프로 연결을 했을떄,

정점1은 사이클이 존재함을 확인할 수 있습니다(아래 그림을 통해 잘 사이클이 발생하는 것을 볼 수 있습니다)

 

DFS에서 사이클을 찾는 방법은 아래의 블로그를 참고하였습니다.

 

https://nicotina04.tistory.com/148

그래프에서 DFS로 사이클 찾기

먼저 bool 배열 3개를 선언해줍니다.

DFS에서 방문처리를 하는 visited배열,

해당 노드를 대상으로 호출한 함수가 종료되었는지 여부를 관리하는 finished배열,

그리고 해당 노드에 사이클이 발생했는지 판별하는 cycle배열입니다.

bool visited[105];
bool finished[105];
bool cycle[105];

다음으로 입력받을 받고, 그래프를 연결하는 함수,

방문 배열을 초기화해주는 함수를 만듭니다.(MAX는 100입니다. n이 최대 100이기 떄문에)

void init(){
    cin >> n;
    for(int i = 1;i<=n;i++){
        int node;
        cin >> node;
        graph[i].push_back(node);
    }
}
 
void clearVisitedArray(){
    for(int i = 1;i<=MAX;i++){
        visited[i] = false;
    }
}

다음으로 DFS함수입니다.

 

DFS 탐색을 하면서 방문하지 않은 노드는 방문하고 만약 해당 노드가 방문된 상태인데

종료가 되지 않았다면(visited == true && finished == false이면)

역방향 간선을 찾았다는 의미입니다. 

 

위 그래프의 경우 방문된 노드를 재확인할 일이 없으므로 사이클이 없습니다

 

위 그래프의 경우 dfs(1), dfs(2), dfs(3)이 차례로 호출된 상태에서

dfs(3)이 1번 노드를 접근하려고 하고 있습니다.

 

이때 1번 노드에 방문은 한 상태지만 dfs(1)의 호출은 아직 끝나지 않은 상태이므로

finished[1] == false이며 back edge 판정이 되고

이 그래프는 사이클을 가짐을 알 수 있습니다.

 

즉, (visited == true && finished == false)가 성립하면, 역방향 간선이 있고,

결국 해당 정점은 사이클을 갖습니다.

cycle == true로 바꿔줍니다.

void dfs(int start){
    visited[start] = true;
    for(int i = 0;i<graph[start].size();i++){
        int y = graph[start][i];
        if(visited[y] == false){
            dfs(y);
        }
        else if(visited[y] == true && finished[y] == false){
           cycle[start] = true;
        }
 
    }
    finished[start] = true;
}

만약 사이클배열이 참이라면,

지금까지 방문한 정점을 모두 set에 넣어줍니다(중복 제거효과도 있음)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define MAX 105
using namespace std;
 
bool visited[105];
bool finished[105];
bool cycle[105];
int n;
vector<int> graph[105];
set<int> allCycleNodes;
set<int>::iterator iter;
 
void init(){
    cin >> n;
    for(int i = 1;i<=n;i++){
        int node;
        cin >> node;
        graph[i].push_back(node);
    }
}
 
void clearVisitedArray(){
    for(int i = 1;i<=MAX;i++){
        visited[i] = false;
    }
}
 
void dfs(int start){
    visited[start] = true;
    for(int i = 0;i<graph[start].size();i++){
        int y = graph[start][i];
        if(visited[y] == false){
            dfs(y);
        }
        else if(visited[y] == true && finished[y] == false){
           cycle[start] = true;
        }
 
    }
    finished[start] = true;
}
 
int main(void){
    init();
    for(int i = 1;i<=n;i++){
        clearVisitedArray();
        dfs(i);
        if(cycle[i] == true){
            for(int j = 1;j<=MAX;j++){
                if(visited[j] == true){
                    allCycleNodes.insert(j);
                }
            }
        }
    }
 
    cout << allCycleNodes.size() << '\n';
 
    for(iter = allCycleNodes.begin();iter != allCycleNodes.end();iter++){
        cout << *iter << '\n';
    }
}