백준 21278 호석이 두 마리 치킨 c++ (플로이드 와샬)

문제 출처 : https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

문제

컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다.

이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다. 건물은 1번부터 N번의 번호를 가지고 있다. i 번째 도로는 서로 다른 두 건물 Ai 번과 Bi 번 사이를 1 시간에 양방향으로 이동할 수 있는 도로이다.

키친 도시에서 2개의 건물을 골라서 치킨집을 열려고 한다. 이 때 아무 곳이나 열 순 없어서 모든 건물에서의 접근성의 합을 최소화하려고 한다. 건물 X 의 접근성은 X 에서 가장 가까운 호석이 두마리 치킨집까지 왕복하는 최단 시간이다. 즉, "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 2개를 골라서 치킨집을 열려고 하는 것이다.

컴공을 졸업한 지 30년이 넘어가는 호석이는 이제 코딩으로 이 문제를 해결할 줄 모른다. 알고리즘 퇴물 호석이를 위해서 최적의 위치가 될 수 있는 건물 2개의 번호와 그 때의 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 출력하자. 만약 이러한 건물 조합이 여러 개라면, 건물 번호 중 작은 게 더 작을수록, 작은 번호가 같다면 큰 번호가 더 작을수록 좋은 건물 조합이다.

입력

첫 번째 줄에 건물의 개수 N과 도로의 개수 M 이 주어진다. 이어서 M 개의 줄에 걸쳐서 도로의 정보 Ai , Bi 가 공백으로 나뉘어서 주어진다. 같은 도로가 중복되어 주어지는 경우는 없다. 어떤 두 건물을 잡아도 도로를 따라서 오고 가는 방법이 존재함이 보장된다.

출력

한 줄에 건물 2개가 지어질 건물 번호를 오름차순으로 출력하고, 그때 모든 도시에서의 왕복 시간의 합을 출력한다.

만약 건물 조합이 다양하게 가능하면, 작은 번호가 더 작은 것을, 작은 번호가 같다면 큰 번호가 더 작은 걸 출력한다.

제한

• 2 ≤ N ≤ 100
• N-1 ≤ M ≤ N×(N - 1)/2
• 1 ≤ Ai , Bi​ ≤ N (Ai  ≠ Bi)

위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 작은 건물 번호를 출력해야 함을 유의하자.

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 플로이드–와샬

풀이

bfs로 잘 풀면 플로이드 와샬보다 빠르게 풀 수 있을 것 같지만, c++로 푼 플로이드 와샬 풀이와 일반적인 NC2 bfs 풀이는 시간 차이가 나지 않았다. c++은 워낙에 빨라서 다 0ms였지만, 다른 언어로 제출하면 미세한 차이를 볼 수 있을 것이다.

아래의 풀이는 플로이드 와샬 풀이이다.

플로이드 와샬은 O(N^3)의 시간 복잡도를 가지기에 N이 100같은 작은 입력 범위에 한해 사용할 수 있다.

플로이드 와샬 알고리즘의 기본 원리는, i에서 i로 가는 거리는 0, i에서 한 번에 갈 수 있는 거리는 주어진 입력에서 증가치가 1로 동일하니 1, 한 번에 갈 수 없는 거리는 INF로 초기화해놓고, 3중 포문으로 모든 정점에서 모든 정점으로 방문하는 최단 거리를 저장한다.

모든 정점에서 모든 정점으로 가는 최단 거리를 알기 때문에, 치킨집을 건설할 두 정점 NC2의 조합 중 거리의 합이 가장 짧은 조합을 출력하면 된다.

거리는 왕복을 출력해야 하니, *2를 해줘야 하고, 오름차순은 애초에 1번 + 2~N, 2번 3~N,~~~ 순의 조합으로 검사하니, 따로 오름차순을 할 필요 없다. 

 

코드

#include <iostream>
#include <algorithm>
#include <tuple>

#define MAX 101
#define INF 987654321
using namespace std;
int n, m;
int graph[MAX];
//플로이드 or bfs 2개 시작 점
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//2<=n<=100
	
	cin >> n >> m;
	int dp[MAX][MAX];
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == j) {
				dp[i][j] = 0;
			}
			else {
				dp[i][j] = INF;
			}
		}
	}

	for (int i = 0; i < m; i++) {
		int from, to;
		cin >> from >> to;
		dp[from][to] = 1;
		dp[to][from] = 1;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
			}
		}
	}
	tuple<int, int, int> answer = make_tuple( INF ,INF,INF);
	for (int i = 1; i <= n; i++) {
		for (int j = i+1; j <= n; j++) {
			int sum = 0;
			for (int k = 1; k <= n; k++) {
				sum += min(dp[i][k], dp[j][k]);
			}
			if (sum < get<2>(answer)) {
				answer = make_tuple(i, j, sum);
			}
		}
	}
	cout << get<0>(answer) << ' ' << get<1>(answer) << ' ' << get<2>(answer) * 2;
	return 0;
}