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

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

bfs를 활용한 문제이다. 문제 조건인 20병의 맥주를 들고 50m마다 한 병씩 마신다.는 최대 1000m를 갈 수 있다는 것을 의미한다. 이를 토대로 너비 우선 탐색 방식을 사용했다. 즉 로직은 아래와 같다.

1. 현재 거리에서 페스티벌까지의 거리가 1000m 이하이면 happy를 출력한다.
2. 1000m 이상이면 반복문을 돌며 편의점들 중 거리가 1000m 이하인 편의점을 찾아 큐에 추가하고 다시 1번으로 간다.
3. 만약 갈 수 있는 편의점이 없다면 sad를 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int t, n;
int homeY, homeX, festivalY, festivalX;
vector<pair<int, int>> shop;
int visit[100];
string result = "";

void bfs() {
	queue<pair<int, int>> q;

	q.push({ homeY, homeX });
	
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		if (abs(festivalY - y) + abs(festivalX - x) <= 1000) {
			result = "happy";
			return;
		}

		for (int i = 0; i < n; i++) {
			if (visit[i]) continue;

			if (abs(shop[i].first - y) + abs(shop[i].second - x) <= 1000) {
				visit[i] = true;
				q.push({shop[i].first, shop[i].second});
			}
		}
	}

	result = "sad";
}

void solution() {
	bfs();

	cout << result << endl;

	shop.clear();
	for (int i = 0; i < 100; i++) {
		visit[i] = false;
	}
}

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

	cin >> t;
	
	while (t--) {
		cin >> n;

		cin >> homeX >> homeY;
		int x, y;
		for (int i = 0; i < n; i++) {
			cin >> x >> y;
			shop.push_back({ y,x });
		}
		cin >> festivalX >> festivalY;

		solution();
	}
	
	return 0;
}