[개쉬운 풀이] 백준 9205 맥주 마시면서 걸어가기 (1일차)

메일 알고리즘 문제 풀기 1일차

 

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

 

 

문제

 

생각

1. 맥주는 20박스이고 한 병당 50미터를 움직일 수 있으므로, 다음 목적지까지 1000거리 이내로 가야한다.

2. 따라서 현재 위치를 기준으로 다음 편의점을 BFS로 탐색하면서 해당 편의점에 도착했을 때, 바로 페스티벌 장소로 도착할 수 있는지 없는지 판별하면 된다.

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_BEER = 20;


struct T{
	int x, y;
};

int t;
int n;
vector<T> v;
T current;
T festival;
int beer = 20;
bool isVisited[101];
bool answer = false;

//v, answer, isVisited
void init(){
	v = vector<T> ();
	answer = false;
	for(int i = 0; i < 101; i++){
		isVisited[i] = false;
	}
}

//두 좌표의 거리 계산
int getDist(T a, T b){
	return abs(a.x - b.x) + abs(a.y - b.y);
}

void findNextDir(T cur){
	queue<T> q;
	q.push(cur);

	while(!q.empty()){
		T now = q.front();	
		q.pop();
		
		if(getDist(now, festival) <= 1000){	//현재 위치에서 페스티벌로 이동가능 여부 판단
			answer = true;
			break;
		}

		for(int i = 0; i < n; i++){
			T tmp = v[i];
			if(!isVisited[i] && getDist(tmp, now) <= 1000){ //편의점 방문 여부 및 거리 판단
				q.push(tmp);
				isVisited[i] = true;
			}
		}
	}
}

void sol(){
	findNextDir(current);
	answer? cout << "happy" << endl : cout << "sad" << endl;
}

int main(){
	cin >> t;
	while(t--){
		cin >> n;
		init();
		cin >> current.x >> current.y;
		for(int i = 0; i < n; i++){
			T tmp;
			cin >> tmp.x >> tmp.y;
			v.push_back(tmp);
		}
		cin >> festival.x >> festival.y;
		sol();
	}	
  return 0;
}