(중요)순환 사이클 판별

욥·2026년 6월 10일

알고리즘 기법

목록 보기

94/98

네이버 블로그 참고.

순환 사이클 판별 중요 예시 그림

1번부터 오름차순이고, 1->2->3->1 은 순환이고,
4->5->1 은 순환이 아니다.
=> 이거를 어떻게 구분할 것인가? 가 관건이다.

dfs를 기반으로 함.

dfs를 기반으로 하므로, visited 변수의 복원은 없다.
따라서 1번과 2번 코드 작성이 가능한 것이다.

1번. 삼색 채색 코드

사이클 판별의 기본
-> 경로 추적시 가시성이 떨어진다고 한다...

#include <iostream>
#include <vector>

using namespace std;

// state[u]는 0, 1, 2 중 하나의 값을 가짐
int state[100001]; 
vector<int> adj[100001];

bool hasCycle(int u) {
    // 1. 현재 노드를 탐색 중(1)으로 표시
    state[u] = 1;

    for (int v : adj[u]) {
        // 2. 이웃 노드가 현재 탐색 중인 노드(1)라면? 
        // -> 현재 경로상의 노드로 되돌아갔으므로 사이클 발견!
        if (state[v] == 1) {
            return true;
        }
        
        // 3. 이웃 노드가 미방문(0)이라면 재귀 호출
        if (state[v] == 0) {
            if (hasCycle(v)) return true;
        }
        
        // 4. state[v] == 2라면 이미 사이클 없음이 증명된 경로이므로 건너뜀 (가지치기)
    }

    // 5. 모든 자식 노드 탐색 완료 -> 탐색 완료(2)로 표시
    state[u] = 2;
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    // ... 그래프 입력 생략 ...

    for (int i = 1; i <= n; ++i) {
        if (state[i] == 0) {
            if (hasCycle(i)) {
                cout << "사이클 발견" << endl;
                return 0;
            }
        }
    }
    cout << "사이클 없음" << endl;
    return 0;
}

2번. 종만북

2개의 flag를 통한 사이클 판별이고,
-> 경로 추적에 용이함.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


vector<vector<int>> vertex(10);
vector<int> visited(10);
vector<bool> finished(10);

int path[10000];

void IsCycle(int here)
{
	visited[here] = true;

	for (int v : vertex[here])
	{
		if (visited[v] == false)
		{
			// 다음 정점. 갈 수 있다. 
			path[here] = v;
			IsCycle(v);

		}
		else if (visited[v] == true && !finished[v])
		{
			cout << v << " 정점 에서 사이클이 발생했다. "
				<< endl;

			cout << "연결되는 정점은 ";
			// 추적하기 
			for (int i = v; i != here; i = path[i])
			{
				cout << i << " ";
			}
			cout << here << " ";
			cout << endl;



		}
		else
		{
			//if (finished[v])
			//	cout << v << "완료" << endl;
		}


	}

	finished[here] = true;
	cout << here << "완료" << endl;
}



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


	vertex[0].push_back(1);
	vertex[0].push_back(3);
	vertex[1].push_back(0); // 이거는 되지 
	vertex[1].push_back(2);
	vertex[2].push_back(3);
	vertex[1].push_back(3);
	//vertex[3].push_back(1); // 안됨. 바로 위에거 주석하고 테스트 하자.
	vertex[3].push_back(0); // 0130 : 순환이다. 
	vertex[3].push_back(4);
	vertex[4].push_back(3);
	vertex[5].push_back(4);

	vertex[0].push_back(6);
	vertex[6].push_back(7);
	vertex[7].push_back(0);



	for (int i = 0; i < 10; ++i)
	{
		cout << "정점 " << i << "에서부터 연결된 정점은 ? ";
		for (const auto& iter : vertex[i])
		{
			cout << iter << " ";
		}
		cout << endl;
	}

	cout << "cycle 확인해보자! " << endl;

	for (int i = 0; i < 10; ++i)
	{

		if (visited[i] == false)
		{
			cout << i << "번 정점 진입하자." << endl;
			IsCycle(i);
		}
		else
		{
			cout << i << " 번 이미 방문함 " << endl;
		}


	}


}