[알고리즘] 21278번: 호석이 두 마리 치킨 (C++)

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

21278번: 호석이 두 마리 치킨

저번에 풀었던 이 문제와 솔루션의 측면에서 비슷하다고 느꼈다.(https://draw-code-boy.tistory.com/191)

1) 모든 정점간의 최단 거리를 구한다.

2) 어떠한 거리를 구하는지 식을 완성하여 도출해낸다.

 

[솔루션]

1) 데이터를 입력받고, 플로이드 와샬을 돌린다.

2) 두 정점을 선택하므로 완전 탐색(브루트 포스)으로 정점 두 개를 택하는 경우를 만든다.

3) 1 ~ n 개의 노드들로부터 두 치킨 집 중 최단 왕복 거리가 나오는 왕복 거리를 골라 다 더 해준다.

4) 더 해준 값들 중, 최솟값과 어느 두 정점을 골라야 최솟값이 나오는지 두 정점을 출력한다.

 

[AC 코드]

#include <iostream>
#define MAX (100 + 1)
#define INF 987654321
using namespace std;

int graph[MAX][MAX];
int n, m;

void floyd() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][k] == INF || graph[k][j] == INF) continue;
				if (graph[i][k] + graph[k][j] < graph[i][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			graph[i][j] = INF;
		}
	}

	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		graph[a][b] = 1;
		graph[b][a] = 1;
	}

	floyd();

	int minValue = INF;
	int ans1 = 0, ans2 = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int sum = 0;
			for (int k = 1; k <= n; k++) {
				sum += min(graph[i][k] + graph[k][i], graph[j][k] + graph[k][j]);
			}

			if (sum < minValue) {
				minValue = sum;
				ans1 = i;
				ans2 = j;
			}
		}
	}

	cout << ans1 << ' ' << ans2 << ' ' << minValue;
	return 0;
}