사이클 찾기: DFS

유향 그래프에서 사이클이 있는지 판단하고, 사이클에 포함되는 노드의 개수가 몇 개인지 세는 알고리즘으로 백준 알고리즘 저지의 9466번: 텀 프로젝트 문제가 이에 해당한다.

9466번: 텀 프로젝트 - Baekjoon Online Judge

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

구글링만 해봐도 해당 문제에 대한 많은 풀이가 존재하지만, 아무래도 이런 로직은 내 코드로 정리하는게 제일 이해도 잘가고 나중에 봐도 이해하기 쉬울 것 같아서 풀이 위주로 정리해봤다. 문제에서는 프로젝트를 함께하고 싶은 학생을 선택하는 것이 나오는데 선택은 한명씩 하게 되있으므로, 각 노드에서 나가는 간선은 하나씩이라는 것을 알 수 있다. 주의해야할 것은 자기 자신도 선택할 수 있으므로 나가는 간선이 자기 자신을 향해서 다시 들어올 수도 있고, 이런 경우도 하나의 사이클로 인정된다는 것이다. 어쨌든 문제에서 노드에서 나가는 간선이 하나라는 것은 우리에게 한가지 정보를 주는데 사이클에 포함된 노드라면 중복해서 다른 사이클에 포함될 수 없다는 것이다. 중복된 사이클이 발생하기 위해서는 적어도 하나의 노드에서 두 개 이상의 간선이 나가야하기 때문에 하나의 간선을 갖는 이상 사이클에 한 번 포함된 노드라면 다시 중복해서 사이클에 들어갈 수 없다.

문제를 보면 제일 먼저 드는 생각은 이 문제는 DFS로 접근해야한다는 것이다. 각 노드를 기준으로 간선을 타보면서 이미 방문한 곳이 다시 나오는지 확인하면 사이클은 손쉽게 구할 수 있다. 말은 쉽지만 막상 해보면 마음대로 되지 않는 것을 확인할 수 있다. 내가 어떤 노드를 중심으로 확인할 수 있는 최대한의 범위에서 사이클이 있나 확인해았을 때, 뒤에 나오게될 노드들이 자기 앞의 어떤 다른 노드를 시작점으로 한 탐색에서 확인을 마친 노드들인지, 이번 탐색에서 탐색을 마친 노드들인지 확인하기가 어렵기 때문이다. 그렇기 때문에 이 문제에서는 방문을 확인하는 배열을 두 개 사용하게 된다. 탐색 자체를 확인하는 vis라는 boolean 배열과 사이클의 확인을 완전히 마쳤다는 의미 fin 배열을 사용해서 vis는 탐색을 하는 동안 true로 업데이트 해주면서 확인을 하고 fin은 완전히 탐색을 마치고 DFS가 종료될때 true로 업데이트 해줌으로써 두 flag의 의미를 구분할 수 있다. 그리고 사이클을 찾게 되었을 때 역으로 왔던 길을 되짚어봄으로써 몇 개가 사이클로 편입되었는지 세어볼 수 있는데, 그냥 DFS를 하나씩 탈 때마다 파라미터로 노드 개수를 세어주는 변수를 하나 들고 다니면 굳이 다시 세어보지 않아도 될듯 하다. 

텀 프로젝트 풀이 소스는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int[] s;
	private static int[] p;
	private static int n;
	private static int T;
	private static boolean[] vis;
	private static boolean[] fin;
	private static int cnt;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		T = Integer.parseInt(br.readLine().trim());

		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(br.readLine().trim());

			st = new StringTokenizer(br.readLine().trim());
			s = new int[n + 1];
			p = new int[n + 1];
			vis = new boolean[n + 1];
			fin = new boolean[n + 1];

			cnt = 0;
			for (int i = 1; i <= n; i++) {
				s[i] = Integer.parseInt(st.nextToken());
			}

			for (int i = 1; i <= n; i++) {
				if (!vis[i]) {
					dfs(i);
				}
//				사이클 확인된 결과 찍어보기
//				for (int j = 1; j <= n; j++) {
//					System.out.print(fin[j] + " ");
//				}
//				System.out.println();
			}
			System.out.println(n - cnt);
		}
	}

	private static void dfs(int idx) {
		vis[idx] = true;
		int next = s[idx];
		if (!vis[next]) {
			p[next] = idx;
			dfs(next);
		} else {
			if (!fin[next]) {
				cycle(idx, s[idx]);
			}
		}
		fin[idx] = true;
	}

	private static void cycle(int idx, int next) {
		cnt++;
		if (idx == next)
			return;
		cycle(p[idx], next);
	}
}