백준 텀 프로젝트(9466)

텀 프로젝트

그래프에서 사이클을 이루지 않는 정점을 구하는 문제. 모든 정점에 대해서 순회 알고리즘(DFS, BFS)을 통해 자기 자신까지 되돌아올때까지 탐색하면 $O(N^2)$으로 풀 수 있다. 하지만 입력이 $10^6$이라서 이 풀이는 불가능하다. 이 문제를 많이 고민 했고, 블로그 풀이도 여럿 찾아보았지만 풀이가 이해는 되는데 직관적으로 와닿지는 않아서 푸는데 오래걸렸다. 이 글에서는 내가 생각한 대로 최대한 직관적으로 풀이하고자 한다.

1. 그래프 이론

어떤 학생이 프로젝트를 함께 하고 싶은 학생을 선택하면 학생 사이에 선택자와 피선택자 관계가 생기는데, 우리는 이를 방향 그래프의 간선으로 생각할 수 있다. 그래프에서 사이클의 정의는 중복되지 않는 간선의 순열인데, 그 중에서 시작점과 끝점이 같은 경우를 말한다. 문제에서 주어지는 한 팀이 될 수 있는 조건은 사이클의 정의와 일치한다. 우리는 이 중에서 사이클에 속하지 않는 정점의 개수를 구하고 싶은데, 이를 구하는 것보다는 반대로 사이클에 속하는 정점 수 $cycle$을 구한 후에 $N - cycle$을 하는 것이 더 쉽다. 모든 정점은 사이클에 포함되거나 포함되지 않기 때문이다.

2. 그래프 탐색

가장 처음에 설명한 것 처럼, $O(N^2)$의 풀이로는 문제의 조건에 맞춰 정답을 찾을 수 없다. 그런데 모든 정점에 대해 사이클을 찾는 알고리즘이 $O(N^2)$의 시간 복잡도를 가지는 이유는 정점들이 중복 방문 가능하기 때문인데, DFS나 BFS를 이용하면 $O(|V| + |E|)$에 가능하므로 이를 이용해보자. 이 풀이에서는 각 정점마다 간선이 하나 뿐이므로 구현이 간단한 DFS를 이용한다.

3. 깊이 우선 탐색

그래프가 연결 그래프라는 보장이 없으므로 모든 정점에 대해서 DFS 함수를 한번씩 호출 해줘야하는데, 우리는 이 과정에서 두가지를 알 수 있다.
1) 방문한 정점이 현재 호출한 DFS함수가 방문했던 정점이라면
그 정점에서 간선을 타고 가면 무조건 자기 자신으로 돌아오게 되고, 그 경로의 길이가 사이클의 크기가 된다.

2) 이전에 호출한 DFS함수가 방문한 지점은 방문할 필요가 없다.
정점 하나에서 시작하는 간선은 하나 뿐인데, 이 간선을 따라가면서 만나는 정점들은 사이클 여부를 이미 확인했기 때문이다.

막상 설명하려고 보니 너무 두서가 없어진 것 같다.

public class Main {
	static int[] adj;
	static boolean[] currentVisit; // 현재 진행되고 있는 DFS함수가 방문했는지 여부
	static boolean[] visit; // 이전의 DFS호출에서 정점을 방문했는지 여부
	
	static int cycle; // 사이클을 이루는 노드의 개수
	
	static void dfs(int here) {
		currentVisit[here] = true;
		int there = adj[here];
		// 이전의 DFS의 호출에서 방문하지 않은 인접 정점을 방문한다
		// 이전에 방문한 정점들은 사이클에 포함되거나 포함되지 않기 때문에 확인해줄 필요가 없다
		if (!visit[there]) {
			if (!currentVisit[there]) {
				dfs(there);
			} else {
				cycle++;
				// 사이클을 이루는 간선의 개수를 센다(간선의 개수가 노드의 개수)
				for (int i = there; i != here; i = adj[i]) cycle++;
			}
		}
		visit[here] = true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < TC; tc++) {
			int N = Integer.parseInt(br.readLine());
			adj = new int[N + 1];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int i = 1; i <= N; i++) adj[i] = Integer.parseInt(st.nextToken());
			currentVisit = new boolean[N + 1];
			visit = new boolean[N + 1];
			cycle = 0;
			for (int here = 1; here <= N; here++)
				if (!visit[here]) dfs(here);
			System.out.println(N - cycle);
		}
	}

}

4. 시간 복잡도

그렇다면 이 풀이의 시간 복잡도는 어떻게 될까? 기존의 DFS에서 약간 변형하긴 했지만, dfs(there)는 해당 정점이 방문하지 않은 정점일 때만 호출되므로 정점을 두번 방문하지 않게 된다.
그렇기 때문에 $O(|V| + |E|)$로 일반적인 DFS와 같게되는데 문제는 사이클의 크기를 계산하는 부분이다. 하지만 이 또한 사이클을 구성하는 원소를 중복으로 세지 않으므로 반복 횟수는 최대 O(|N|)임을 알 수있고 최종 시간 복잡도는 $O(|N| + |N|)$이 된다.