9205 맥주 마시면서 걸어가기

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

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

 

(풀이)

1. 잘못 접근. 문제에서 순차적으로 접근해야 하는줄 알았다.

 

2. 순서에 상관없이, 편의점 혹은 도착지점 까지 BFS 탐색을하며 목적지까지 맥주가 다 떨어지지 않는지

풀어야 한다.

 

3. 맥주가 다 떨어지는 것은 탐색까지 도착지에 다다르지 못하면 도착 하지 못한것으로 판정

 

4. 다음 위치를 가기 위한 조건 즉, queue에 삽입 되어야 하는 조건 check[i] = (i는 편의점 혹은 도착지)에

방문하지 않은지점이고 && distance(맨해튼 거리) <= 1000 이하인지 살펴야한다

 

여기서 중요한 부분은 distance /50 - 20 <=0 인걸로 하면 100%에서 터지는데

그 이유는 만약 거리가 1005면 1000까지 가고 맥주가 떨어진다 5미터가 남는데

나누기 연산으로 정수형 연산을하면 저 조건에 맞는다고하여 가능하다는 오류를 범할 수 있다.

 

따라서 나누기 연산일때는 나머지가 생기는지도 판단하고, 바람직하다면, 상수로 처리해주면 더 편하다.

 

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

int N;

bool check[101];
queue<pair<int, int>> q;
vector<pair<int, int>> locations;
int T; // test case
void go_festival();
bool isfind = false;
int main(void)
{
	cin >> T;
	while (T--)
	{
		cin >> N;
		int x = 0, y = 0;
		for (int i = 0; i < N + 2; ++i)
		{
			cin >> x >> y;
			locations.push_back(make_pair(x, y));
		}
		q.push(make_pair(locations[0].first,locations[0].second));
		check[0] = true;
		go_festival();
		if (!isfind)
		{
			cout << "sad" << '\n';
		}
		isfind = false;
		while (!locations.empty()) { locations.pop_back(); }
		while (!q.empty()) { q.pop();}
		for (int i = 0; i < N+2; ++i)
			check[i] = false;

	}

	return 0;
}

void go_festival()
{
	int RockFestival_pos = locations.size()-1;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if (x == locations[RockFestival_pos].first && y == locations[RockFestival_pos].second)
		{
			cout << "happy" << '\n';
			isfind = true;
			return;
		}

		for (int i = 1; i < locations.size(); ++i)
		{
			int xn = locations[i].first;
			int yn = locations[i].second;


			int tmp_xn = xn - x;
			int tmp_yn = yn - y;

			if (tmp_xn < 0) tmp_xn = -tmp_xn;
			if (tmp_yn < 0) tmp_yn = -tmp_yn;

			int distance = tmp_xn + tmp_yn;

			if (check[i] == false && ((distance/50)-20 <= 0))
			{
				check[i] = true;
				q.push(make_pair(xn, yn));
			}
		}
	}


}