[BOJ 23324 // C++] 어려운 모든 정점 쌍 최단 거리

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

 

이번에 볼 문제는 백준 23324번 문제인 어려운 모든 정점 쌍 최단 거리이다.
문제는 아래 링크를 확인하자.

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

23324번: 어려운 모든 정점 쌍 최단 거리

주어진 그래프는 연결그래프라는 점을 잘 이용해보자.

 

주어진 그래프에서 가중치가 1인 간선을 지웠을 때, 해당 그래프는 (1)연결그래프이거나 (2)연결요소가 둘인 그래프로 바뀌게 될 것이다. 각 경우의 답이 어떻게 나오는지 살펴보자.

 

(1) 연결그래프일 경우, 어떤 두 노드를 골라도 가중치가 0인 간선만을 이용하여 서로를 연결하는 경로가 존재하므로 답은 0이 된다.

 

(2) 연결요소가 둘인 그래프로 바뀌게 되면 같은 연결요소 안의 두 노드를 고르면 둘 사이 최단경로는 0, 각 연결요소에서 하나씩의 노드를 고르면 둘 사이 최단경로는 1이 된다. 따라서 각 연결요소의 크기를 구해 곱한 값이 답이 된다.

 

위의 내용을 구현해 문제를 해결하자. 그래프의 연결요소의 크기는 dfs나 bfs와 같은 그래프 탐색 알고리즘 또는 disjoint set과 같은 자료구조를 이용해 간단히 구할 수 있다.

 

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

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll N, M, K;
vector<int> G[100001];
bool visited[100001];

ll dfs(int cur) {
	ll ret = 1;
	for (auto& node : G[cur]) {
		if (visited[node]) continue;
		visited[node] = 1;
		ret += dfs(node);
	}
	return ret;
}

int X, Y;

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

	cin >> N >> M >> K;
	for (int k = 1; k <= M; k++) {
		int x, y; cin >> x >> y;
		if (k == K) X = x, Y = y;
		else {
			G[x].emplace_back(y);
			G[y].emplace_back(x);
		}
	}
	
	visited[X] = 1;
	ll cnt1 = dfs(X);
	if (visited[Y]) {
		cout << 0;
		return 0;
	}

	visited[Y] = 1;
	ll cnt2 = dfs(Y);

	cout << cnt1 * cnt2;
}