백준 9205_맥주 마시면서 걸어가기(C++)

 

www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

[문제 풀이]

플로이드-워셜(Floyd Warshall)을 이용하여 문제를 풀었습니다.

 

이 문제는 상근이가 시작 지점에서 끝 지점까지 50미터당 맥주 한 병을 멈추지 않고 마시면서 갈 수 있는가를 구하는 문제였습니다. 가는 길에 편의점이 있으면 편의점을 들를 수 있고 최대 수용량 맥주 20병을 채울 수 있습니다. 즉 시작 지점 A 노드에서 도착지점 Z로 갈 수 있는 모든 경로를 탐색하며 음수도 처리 가능한 플로이드-워셜(Floyd Warshall) 알고리즘을 이용하면 문제를 해결할 수 있습니다.

 

코드 설명

• 좌표들을 벡터에 저장해 둔 후, 좌표들의 거리를 계산하여 거리가 50미터 이상이면 INF를 이하이면 1을 2차원 배열 path에다 저장해 줍니다.
• 저장 후, 배열을 순회하며 i -> j 로 가는 경로가 있거나 i -> k -> j 로 가는 경로가 있으면 path[i][j]에 1을 저장해 줍니다.
• 모든 로직이 종료된 후 path[시작지점][도착지점]이 1일 경우 happy를 출력해 줍니다.

[코드]

#include<iostream>
#include<math.h>
#include<vector>

using namespace std;

#define INF 2

int main() {

	int T; cin >> T;

	int path[104][104];

	for (int test = 0; test < T; test++) {

		int n; cin >> n;

		vector<pair<int, int>> vertex;

		for (int i = 0; i < n + 2; i++) {
			int temp1, temp2;
			cin >> temp1 >> temp2;

			vertex.push_back(make_pair(temp1, temp2));
		}

		for (int i = 0; i < vertex.size(); i++) 
			for(int j = 0; j < vertex.size(); j++)
				if (i == j)
					path[i][j] = 1;
				else {
					int distance = abs(vertex[i].first - vertex[j].first) + abs(vertex[i].second - vertex[j].second);
					if (distance > 1000)
						path[i][j] = INF;
					else
						path[i][j] = 1;
				}
				
		for (int k = 0; k < vertex.size(); k++)
			for (int i = 0; i < vertex.size(); i++)
				for (int j = 0; j < vertex.size(); j++)
					if (i == j)
						continue;
					else if (i == k || k == j)
						continue;
					else if (path[i][j] == 1 || (path[i][k] == 1 && path[k][j] == 1))
						path[i][j] = 1;

		if (path[0][vertex.size() - 1] == 1)
			cout << "happy" << endl;
		else
			cout << "sad" << endl;

	}

	return 0;

}