(백준 9205번 맥주 마시면서 걸어가기) (라이님 블로그 대회 알고리즘 따라잡기 18) 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

플로이드 와샬 알고리즘 문제인지 모르고 봤다면 푸는게 좀 난해했을 것 같은 문제다..!

 

백준 9205번

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

 

집과 n개의 편의점, 그리고 축제 장소가 2차원 공간에 있지만 하나의 그래프 노드라고 생각하면 문제가 쉽게 풀린다!

두 점 사이의 맨해튼 거리가 1000이 넘으면 맥주가 부족해 도착하지 못하므로 1000을 기준으로 각 노드들(집, 편의점, 축제 장소)가 이어져 있는지를 우선 dist matrix에 0과 1을 이용해 표시한다.

 

다음 플로이드 마샬 알고리즘을 이용해 집에서 축제 장소까지 연결된 루트가 있는지 확인해주면 끝!

 

대칭(symmetric matrix)이기 때문에 distance matrix와 플로이드 와샬 알고리즘을 upper triangle에 대해서만 수행하면 시간을 좀 더 단축할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;

int Manhattan_dist(int x1, int y1, int x2, int y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int TC; cin >> TC;
	while (TC--) {
		int n; cin >> n;
		vector<P> loc(n + 2); // location (0 : home, 1 ~ n : convinient store, n+1 : festival)
		for (int i = 0; i < n + 2; i++) {
			cin >> loc[i].first >> loc[i].second;
		}

		int dist[102][102] = { 0 };
		for (int i = 0; i < n + 2; i++) {
			for (int j = i; j < n + 2; j++) {
				if (i == j) continue;
				int x1 = loc[i].first, y1 = loc[i].second;
				int x2 = loc[j].first, y2 = loc[j].second;
				int distance = Manhattan_dist(x1, y1, x2, y2);
				if (distance > 1000) dist[i][j] = 0;
				else dist[i][j] = 1;
				dist[j][i] = dist[i][j];
			}
		}

		for (int k = 0; k < n+2; k++) {
			for (int i = 0; i < n + 2; i++) {
				if (dist[i][k] == 0) continue;
				for (int j = i; j < n + 2; j++) {
					if (i == j) continue;
					if (dist[k][j] != 0) {
						dist[i][j] = 1;
						dist[j][i] = 1;
					}
				}
			}
		}

		if (dist[0][n + 1] == 1) cout << "happy\n";
		else cout << "sad\n";
	}

	return 0;
}