[백준 9466] 텀 프로젝트 - 위상정렬 풀이

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

9466번: 텀 프로젝트

 

---

이 문제를 처음 풀고나서 위상정렬 푼 것이 조금 마음에 들지 않아서 구글링을 했었다. 검색한 블로그들을 읽어보니 DFS를 이용한 좋은 풀이 방법이 존재했다. 

대부분의 블로그들이 다 똑같은 풀이 방법만 적혀 있었기 때문에, 내가 푼 다른 풀이를 적어놓기로 했다. 개인적으로 문제를 풀 때 다양한 풀이 방법을 접해보는 것이 좋다고 생각하기 때문이다.

 

---

 

문제를 읽었을 때 다음과 같은 풀이들을 생각했다.

 

• 모든 정점(학생)에 대해 DFS 

- 문제점 1 : 방문 체크를 하면서 DFS를 해야하는데 자기 자신을 처음에 방문체크하면 나중에 방문했던 정점을 만났을 때 처음 시작점에 대한 정보가 없어서 싸이클인지 알 수 없다.

ex. 1 - 2 - 3 - 1  이라면 1 부터 DFS를 해서 3까지 왔을 때, 이미 방문한 점인 1이 싸이클을 완성하는 정점인지, 이전에 다른 경우에서 방문했던 정점인지, 중간에 방문했던 정점인지 알 수가 없다. 해당 정보를 전달하면서 DFS를 진행하는 방법은 떠오르지 않았다.

- 문제점 2 : 다음과 같은 경우를 생각해보았다.

학생 1 -> 2 / 학생 2 -> 3 / 학생 3-> 4/ ..... / 학생 n-1 -> n / 학생 n -> n 

위와 같은 경우 1에서 DFS를 한다면 총 n번, 2는 n-1번, 3은 n-2번... 총 n * n/2 번을 방문하게 된다. 정점의 개수가 n이므로 이 방법은 무조건 시간초과가 발생할 것이다.

 

• 유니온 - 파인드

학생의 번호를 부모, 학생이 선택한 다른 학생을 자식으로 두고 유니온 파인드를 통해 집합을 만들 수 있지 않을까? 라는 생각을 해봤지만 싸이클을 체크할 수 있는 방법은 전혀 떠올리지 못했다.

 

 

---

 

위 2가지 경우의 풀이를 포기하고 위상정렬로 풀이가 가능한가에 대해 생각해보았다. 위상정렬이 싸이클을 판별하는 대표적인 방법 중 하나이기 때문이다. 또한 해당 문제는 학생이 다른 학생을 가리키고 있으므로 명백히 DAG 라고 볼 수 있다. 

 

하지만 이 풀이도 문제가 발생한다고 생각이 들었다. 학생이 자기 자신을 가리킬 때는 결과가 틀리게 나올 것 같았기 때문이다. 아래는 문제의 예제 입력 중 첫 번째 case 이다.

위 그래프를 위상정렬할 때 deg 와 queue를 정리해보면

deg[1] = 1 , deg[2] = 0, deg[3] = 2, deg[4] = 1, deg[5] = 0, deg[6] = 1, deg[7] = 1 이 되고 q에는 {2,5} 가 들어간다.

 

deg[3] = 2의 경우 자기 자신을 가리키는 edge는 포함하지 않은 경우이다.

위 내용대로 위상정렬을 할 경우 1과 5를 방문하면서 deg[3] 은 0 이 되고 싸이클을 이루지 않는다는 결과가 나올 것이다. 따라서 틀린 답이 나오게 된다.

또한 deg[3] 에 자기 자신을 가리키는 edge도 포함해 증가시키고 graph[3] 에 넣더라도 3이 3을 방문하면서 deg[3] = 0 이 되지않을까 하는 생각이 들었다.

 

하지만 3이 3을 방문하면서 0 이 되는 경우는 발생할 수 없다. 1과 5에 방문해서 deg[3] 이 3에서 1이 되었다고 하더라도, 0이 되지않으므로 deg[3] 은 q에 들어가지 않는다. 3이 q에 들어가려면 3->3 edge가 위상정렬이 진행되면서 지워져야 하는데 이는 절대로 발생할 수 없다. 3을 방문함으로써 3->3 edge가 지워지는데 3->3edge 때문에 deg[3] 이 0 이 되지 않기 때문이다. 

 

따라서 그냥 평범한 위상정렬 처럼 진행해도 상관이 없다. 매 Test case 마다 위상정렬을 진행한 후에 deg값이 0인 정점을 세어주고 출력하면 된다. 마지막에 graph 벡터와 deg 배열을 초기화 해주기만 하면 된다.

 

---

 

Code

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <map>
#include <string>
#include <string.h>
#include <cstring>
#include <cmath>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define INTMAX 2'100'000'000
#define MOD 1'000'000'007

using namespace std;

int deg[100001];
vector <int> v[100001];
int t,n;

void topology() {
	queue <int> q;

	for (int i = 1; i <= n; i++) {
		if (!deg[i])
			q.push(i);
	}

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		for (int i : v[cur]) {
			deg[i]--;
			if (!deg[i])
				q.push(i);
		}
	}
}

int main() {
	fastio;

	cin >> t;

	while (t--) {
		int cnt = 0;
		memset(deg, 0, sizeof(deg));
		

		cin >> n;
		
		int x;
		for (int i = 1; i <= n; i++) {
			cin >> x;
			deg[x]++;
			v[i].push_back(x);
		}

		topology();

		for (int i = 1; i <= n; i++) {
			if (!deg[i])
				cnt++;
		}

		for (int i = 1; i <= n; i++) {
			if (!deg[i])
				cnt++;
		}

		cout << cnt << endl;

		for (int i = 1; i <= n; ++i) {
			v[i].clear();
		}
	}
}

 

vector graph[100001] 은 보통 메모리 초과가 나지만 위 문제의 경우 edge가 무조건 n개만 존재하기 때문에 메모리 초과가 발생하지 않는다. 같은 이유로 q로 인한 메모리 초과나 graph 배열을 clear 할 때 시간초과 같은 것은 발생하지 않는다.

 

위상 정렬은 싸이클이 없는 정점만 방문하므로 시간은 O(n) 이다. n <= 100,000 이므로 시간초과는 발생하지 않는다.