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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘: 밸만포드

(1) 코드 10~12

 조건을 따라 두 좌표 사이의 거리를 구하는 함수를 만들어줍니다.

(2) 코드 27~39

 출발지(index : 0)가 정해져 있습니다. 따라서 밸만포드를 구현해주었습니다.
 boolean 배열을 하나 만들어 출발지에서 해당 index로 도착 가능한지 체크를 해주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	// 벨만포드
	typedef pair<int, int> pii;
	const int DMAX = 1000.0;
	int T, N;
	pii arr[111];
	bool CanGo[111];
	int Dist(pii a, pii b){
	return abs(a.first-b.first)+abs(a.second-b.second);
	}
	int main(){ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	cin >> T;
	while(T--){
	cin >> N;
	for (int i = 0; i < N+2; ++i){
	int x, y;
	cin >> x >> y;
	arr[i] = pii(x,y);
	}
	// 초기화
	memset(CanGo,false,sizeof(CanGo));
	CanGo[0] = true;
	// 벨만포드
	for (int k = 0; k < N+2; ++k){
	for (int i = 0; i < N+2; ++i){
	// i에 갈 수 없으면 continue
	if(!CanGo[i]) continue;
	for (int j = 0; j < N+2; ++j){
	// i에서 j 갈 수 있으면 최신화
	if(Dist(arr[i],arr[j])<=DMAX){
	CanGo[j] = true;
	}
	}
	}
	}
	if(CanGo[N+1]) cout << "happy" << '\n';
	else cout << "sad" << '\n';
	}
	return 0;
	}

view raw BOJ 9205.cpp hosted with ❤ by GitHub