백준 9466 텀 프로젝트

 

그래프에서 사이클 구간 찾는 문제

문제 이해 자체는 쉬운데 구현이 어려웠다

사이클을 찾아야 하는데, 다른 사람들 글을 보니까 finish배열을 써서 finish가 체크가 아닌데 visit는 체크이면 사이클이고 그런다던데 뭔소린지 직관적으로 이해되지 않아서 이해하는 데 좀 걸렸다

 

1. 사이클 확인

그래서 내 나름대로 이해해 보았는데, finish배열말고 아래처럼 생각하면 좋더라

void dfs(int now) {
	int next = v[now]; //가리키는 거
	if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다
		//구현
	}

	visit[now] = 1;
	dfs(next); //다음 경로
}

 

dfs를 돌면서 보통 이렇게 방문을 체크하고, 방문하지 않았으면 dfs를 또 돌리는 식으로 코딩한다

if(!visit[now]) { ... } //방문하지 않았으면~

 

그러면 다시 말해서, 다시 이 if문을 보러 왔다는 의미 자체가 이전 노드에서 조건 합격해서 탐색을 보냈다는 것이다

그런데 이 if문에서 방문을 했다고(즉, visit[now]==1) 되어버리면?

이전에 방문했는데 또 탐색하러 왔다 = 사이클

이런 의미가 된다

 

그래서 위에 코드에서 if문에 들어왔다는 것 자체가 사이클이 있다는 의미이게 된다

if문 안에서 찐 사이클을 찾아주기만 하면 된다

 

2. 사이클 찾기

사이클이 있다고 확인했으니, 방문했던 노드 중에서 찐 사이클을 찾아야 한다

왜 이런 과정이 필요하냐면, 위에처럼 1->4->7->6->4 사이클이 생겼다고 생각해 보자

여기서 사이클은 4->7->6->4인데 방문은 1,4,7,6,4이다. 1은 사이클이 아니므로 제외되어야 한다

 

나는 방문했던 노드를 전부 vector배열에 저장해둔 뒤, 그 vector배열에서 사이클이 시작된 위치를 찾았다.

그리고 거기서부터 끝까지가 사이클이다 라고 구현했다

 

void dfs(int now, vector<int> &cycle) {
	int next = v[now]; //가리키고 있는 쪽
	cycle.push_back(now);
	if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다
		if (cycle.size() == 0) return;

		int i;
		for (i = 0; i < cycle.size(); i++) { //사이클인 부분의 인덱스를 찾음
			if (cycle[i] == v[now]) break;
		}

		for (int j = i; j < cycle.size(); j++) {
			done[cycle[j]] = 1; //사이클에 소속된 사람들 체크
		}
		return;
	}

	visit[now] = 1;
	dfs(next, cycle); //다음 경로
}

이 코드로 생각하면 위의 그림같은 경우에 vector배열에 저장된 숫자는 1,4,7,6이겠고

i는 1이고, 1부터 끝까지(4,7,6)가 사이클로 체크되겠다

 

3. 전체 코드

메인 함수를 추가하면 이렇게 된다

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <memory.h>
using namespace std;
//2차원 배열 쓰면 size오버 - 1차원 배열로 사이클 탐지 필요
int visit[100001], done[100001];
int n;
vector<int> v;
void dfs(int now, vector<int> &cycle) {
	int next = v[now]; //가리키는 거
	cycle.push_back(now); //방문한 애들 저장
	if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다
		if (cycle.size() == 0) return; //암것도 없으면 패스

		int i;
		for (i = 0; i < cycle.size(); i++) { //방문한 애들 중에 사이클이 시작되는 인덱스를 찾음
			if (cycle[i] == v[now]) break;
		}

		for (int j = i; j < cycle.size(); j++) {
			done[cycle[j]] = 1; //사이클에 소속된 사람들 체크. 시작 인덱스부터 끝까지는 다 사이클임
		}
		return;
	}

	visit[now] = 1;
	dfs(next, cycle); //다음 경로
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		v.resize(n + 1);
		for (int i = 1; i <= n; i++) {
			cin >> v[i];
		}
		for (int i = 1; i <= n; i++) {
			if (!visit[i]) {
				vector<int> cycle;
				dfs(i, cycle); //사이클 세기
			}
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (done[i] == 0) cnt++;
		}
		cout << cnt << "\n";

		cnt = 0;
		v.clear();
		memset(visit, 0, sizeof(visit));
		memset(done, 0, sizeof(done));
	}
}