그래프의 사이클을 구하는 알고리즘

HUSII·2023년 7월 8일

알고리즘

목록 보기

1/6

그래프의 노드와 엣지가 주어졌을때, 해당 그래프의 사이클이 몇개인지 혹은 사이클에 속하는 노드가 어떤노드인지, 또 몇개인지 구하는 알고리즘

대표 문제 - 백준 9466

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

노드와 엣지가 주어졌을때 사이클에 속하지 않는 노드가 몇개인지 구하는 문제이다.

방법

dfs를 이용한 알고리즘이다.
먼저 visited, done 배열을 준비한다.

visited 배열은 해당 노드를 방문했는지 체크하는 배열이고,
done 배열은 해당 노드의 사이클을 확인했는지 체크하는 배열이다
먼저 코드를 보고 그림으로 설명하겠다.

void baekjoon::dfs(int nodeNum) {
	visited[nodeNum] = true;
	int next = member[nodeNum];

	if (!visited[next])
		dfs(next);
	else if (!done[next])
	{
    	/* 방문은 했지만(visited[next] = true),
        ** done[next] = false
        ** -> 한바퀴 돌았다는 뜻
        ** -> 사이클이 생성된걸 확인,
        ** 사이클에 해당하는 마지막 노드
        */
        
		//팀원을 모두 센다
		for (int i = next; i != nodeNum; i = member[i])
			cnt++;
		cnt++; //자기 자신을 센다
	}
    
    /* case1
    ** 사이클에 해당하는 노드이지만,
    ** 이전 노드가 이미 count 했음
    ** -> done[자기자신]만 true해주고 끝냄
    */
    /* case2
    ** 사이클에 해당하지 않는 노드
    */
    
    //더 이상 해당 노드를 방문할 일이 없다
	done[nodeNum] = true;
}

그림 설명

위와 같은 노드와 엣지가 있다고 하자.
여기서 (1,2,3), (5)가 사이클을 형성하고 있다.

첫번째 케이스(일반적인 사이클)

여기서 1번부터 dfs로 체크한다.
visited[1] = true &
visited[edge[1]] = false -> 2번 노드로 이동

visited[2] = true &
visited[edge[2]] = false -> 3번 노드로 이동

visited[3] = true &
여기서 visited[edge[3]] = visited[1] = true인데
done[1] = false이기 때문에,
이는 사이클이 확인됐다는 뜻이다. 따라서
3번이 한바퀴돌아서 사이클에 해당하는 노드를 체크해준다.
사이클에 해당하는 노드인 1,2,3의 done값을 모두 true로 설정한다.