취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 7827번 문제인 Transitive Closure이다.
문제는 아래 링크를 확인하자.

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

지문에 Transitive Closure이라는 cp에서 자주 보이지는 않는 용어가 등장하지만 문제의 설명만으로도 충분히 구해야하는 것을 알 수 있다. 주어진 방향그래프 위에서 점 $r$로부터 점 $c$로 가는 경로가 존재하면 $r$행 $c$열 성분이 1, 아니면 0인 $V$행 $V$열의 1의 개수, 즉 각 점으로부터 도달가능한 (자기 자신이 아닌) 점의 개수의 합을 구하자.

모든 점에서 다른 점으로의 도달 가능성을 확인하는 것은 지문에서 언급된 방법인 (Floyd-)Warshall 알고리즘을 사용하는 것으로도 가능하지만 이 문제에서 사용하기에는 시간복잡도가 크다. 그러면 이 문제를 어떻게 해결해야 할까?

이 문제에서는 이동 거리에는 신경쓸 필요 없이 이동 가능성만을 고려하면 된다는 점에 주목하자. 이 점에 주목하면 Floyd-Warshall 알고리즘까지 사용할 필요 없이 각 점을 시작점으로 하는 그래프 탐색 알고리즘(DFS, BFS)을 사용해 문제를 해결할 수 있음을 관찰할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

int V, E;
vector<int> G[2501];
int visited[2501];
queue<int> que;
int ans;

void solve() {
	ans = 0;
	cin >> V >> E;
	for (int v = 1; v <= V; v++) G[v].clear();
	while (E--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
	}

	for (int i = 1; i <= V; i++) {
		memset(visited, 0, sizeof(visited));
		visited[i] = 1;
		que.push(i);
		int cnt = -1;
		while (!que.empty()) {
			int cur = que.front(); que.pop();
			cnt++;
			for (auto &nxt:G[cur]) {
				if (visited[nxt]) continue;
				visited[nxt] = 1;
				que.push(nxt);
			}
		}
		ans += cnt;
	}
	cout << ans << '\n';
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}