그래프 이론 - cycle 찾기( + cycle 길이)

dfs 이용해서 그래프에서 cycle 찾아내기

 

dfs로 cycle을 찾아내는 원리는 back edge를 찾는 것이 핵심인데,

back edge를 찾기 위해서 노드의 상태에 visit 에 더해서 finished 라는 상태를 하나 더 추가해준다.

visit은 해당 노드 탐색을 시작할 때 켜지고, finished는 해당 노드에서 dfs를 다 돌고 오면 켜진다.

 

따라서

"현재노드 -> 다음노드"의 한 edge를 보는 경우,

다음노드의 visit 상태는 켜져있지만 아직 finished가 켜지지 않은 경우라면

해당 edge가 back edge임을 알게된다.

 

우선, cycle의 개수만 새는 경우에는 visit을 단순히 bool로 선언해줘도 된다

--> 참고하면 좋은 문제 :  백준 16724번

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

16724번: 피리 부는 사나이

정답 코드

#include <iostream>
using namespace std;

int N, M;
char map[1000][1000];
bool visit[1000][1000];
bool finished[1000][1000];
int didj[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

int cycle = 0;

void dfs(int i, int j) {
	visit[i][j] = true;

	int ni = i;
	int nj = j;
	if (map[i][j] == 'D') ni++;
	else if (map[i][j] == 'U') ni--;
	else if (map[i][j] == 'R') nj++;
	else nj--;

	if(!visit[ni][nj]) dfs(ni, nj);
	else if(!finished[ni][nj]) cycle++;

	finished[i][j] = true;
}

int main() {
	scanf("%d%d", &N, &M);
	
	char row[1001];
	for (int i = 0; i < N; i++) {
		scanf("%s", row);
		for (int j = 0; j < M; j++) {
			map[i][j] = row[j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!visit[i][j]) dfs(i, j);
		}
	}
	printf("%d", cycle);
}

원리는 위에서 말한 것과 같고, 이제 여기서

cycle의 개수 말고 길이까지 알고싶다고 하면

단순하게 visit 을 bool이 아닌 int로 선언해준 다음

dfs order를 저장해주면 된다

 

저장해준 후, cycle을 발견했을 때 해당 back edge에 연결된 노드들의 dfs order를 비교해

cycle의 길이를 판단한다.

 

--> 참고하면 좋은 문제: 백준 9466번

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

9466번: 텀 프로젝트