[백준/BOJ] 백준 9205번 : 맥주 마시면서 걸어가기

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

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

현재 지점에서 갈 수 있는 위치를(50미터*맥주 20병은 1000이므로 현재 지점에서 1000미터 이내 거리만 갈 수 있다) bfs를 통해 페스티벌에 맥주의 문제없이 잘 도착할 수 있는지 확인한다

 

코드

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

int n;
int discoverd[102]; //집의위치 + 편의점의 위치(편의점은 최대 100개) + 페스티벌위치

void Solve(pair<int, int> home, vector<pair<int, int>> site, pair<int, int> festival)
{
	discoverd[0] = 1; //출발(집)지점을 0으로 한다

	queue<pair<int, int>> q;
	q.push(home);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//페스티벌에 도착했을때
		if (here.first == festival.first && here.second == festival.second)
		{
			cout << "happy" << "\n";
			return;
		}

		//편의점들의 위치와 페스티벨의 위치는 1~site.size() 로 한다
		for (int i = 1; i <= site.size(); i++)
		{
			pair<int, int> there = site[i - 1];

			//갈 수 있는 위치(50미터*맥주20병은 1000이므로 현재 지점에서 1000미터 이내 거리만 갈 수 있다)이고, 발견된 적이 없을때
			if (abs(here.first - there.first) + abs(here.second - there.second) <= 1000 && discoverd[i] == 0)
			{
				//i지점 발견표시 
				//편의점들의 위치와 페스티벨의 위치는 1~site.size() 로 한다 (0은 집의 위치)
				discoverd[i] = 1;

				q.push(there);
			}

		}
	}

	cout << "sad" << "\n";
}

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

	int t;
	pair<int, int> home;
	vector<pair<int, int>> market;
	pair<int, int> festival;
	vector<pair<int, int>> site;
	int x, y;

	cin >> t;

	for (int test = 0; test < t; test++)
	{
		memset(discoverd, 0, sizeof(discoverd));
		market.clear();
		site.clear();

		cin >> n;

		cin >> x >> y;
		home = make_pair(x, y);

		for (int i = 0; i < n; i++)
		{
			cin >> x >> y;
			market.push_back(make_pair(x, y));
		}

		cin >> x >> y;
		festival = make_pair(x, y);

		//site에 편의점의 위치와 페스티벌의 위치를 저장한다
		site = market;
		site.push_back(festival); 

		Solve(home, site, festival);
	}

	return 0;
}