백준 11581 : 구호물자

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

Cycle이 존재하는지 묻는 문제이다.

그래프의 시작점은 1부터 시작해서 n까지 도착하는 것이고

모든 그래프를 탐색하면서 도중에 Cycle이 돌면 안된다.

Cycle이 도는지 검사하는 것은 여러가지 방법이 있지만

이 문제에서는 이미 그래프가 주어졌고 그래프의 노드를 모두 탐색하는 것이므로

DFS를 사용한다.

Stack을 이용한 DFS도중에 만약 이미 visited한 점을 만났다면 그것이

이전에 되돌아가서 visited 체크된것인지 아니면 이미 방문해서 visited가 된것인지 확인해야 한다.

만약 Stack에 이미 visited 체크된 노드가 존재한다면 이미 방문한 노드이기 때문에 cycle이 발생한다.

만약 visited 체크된 노드이지만 Stack에는 들어있지 않다면 다시 되돌아오면서 이미 방문한 지점이기때문에

그냥 넘어가도 무방하다.

어떤 그래프의 사이클 검사의 가장 기본이므로 이 코드를 잘 숙지해놔야겠다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <iostream> #include <vector> using namespace std; int n; vector<int> node[101]; bool visited[101] = {false, }; bool isCycle(int init){ vector<int> v; v.push_back(init); visited[init] = true; while(!v.empty()){ int curIndex = v.back(); //현재 인덱스에서 다음 인덱스를 찾는다 bool flag = true; for(auto it = node[curIndex].begin(); it != node[curIndex].end(); it++){ if(visited[*it]){ //다음 노드가 이미 방문한 곳임 //만약 이 *it 인덱스가 이미 stack(v)에 들어있다면 cycle 발생 for(auto cy = v.begin(); cy != v.end(); cy++){ if(*cy == *it){ //cycle발생. return true; } } }else{ //다음 노드로 dfs한다. visited[*it] = true; v.push_back(*it); flag = false; break; } } if(flag){ //방문할 다음 노드가 없을 경우. v.pop_back(); } } //여기까지 return true 로 안넘어가고 무사히 //dfs가 수행되었으면 Cycle이 존재하지 않음. return false; } int main(){ cin >> n; for(int i = 1; i <= n-1; i++){ int s; cin >> s; for(int j = 1; j <= s; j++){ int link; cin >> link; node[i].push_back(link); } } if(isCycle(1)){ cout << "CYCLE" << endl; }else{ cout << "NO CYCLE" << endl; } return 0; }