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

문제

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

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

 

 

문제풀이

 

BFS로 풀었다.

집, 편의점, 락 페스티벌 좌표를 입력한다.

맥주 한 병에 50m, 최대 20병이기 때문에 집에서 출발하거나 편의점에서 출발했을 때 최대 1000m 범위 안에 있는 거리를 갈 수 있다.

집 좌표를 큐에 넣고 편의점 하나하나 비교해보면서 방문한 적이 없고, 거리가 1000m 이하인 편의점이 있으면 좌표를 큐에 집어넣는다.

좌표를 큐에 집어넣었으면 방문 표시를 한다.

지금 있는 좌표에서 락 페스티벌까지의 거리가 1000m 이하라면 갈 수 있으므로 happy를 출력한다.

만약 갈 수 있는 편의점, 락 페스티벌이 없으면 큐가 비므로 sad를 출력한다.

 

 

코드

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


vector<pair<int, int>>cvs;
vector<bool>visit;
pair<int, int>rock;
int start_y, start_x;
int n;
int i;

void Move() {
	queue<pair<int, int>>q;
	q.push({ start_y, start_x });
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		if (abs(y - rock.first) + abs(x - rock.second) <= 1000) {
			cout << "happy";
			return;
		}
		else {
			for (i = 0; i < cvs.size(); ++i) {
				if (abs(y - cvs[i].first) + abs(x - cvs[i].second) <= 1000) {
					if (!visit[i]) {
						visit[i] = true;
						q.push({ cvs[i].first, cvs[i].second });
					}
				}
			}
		}
	}
	cout << "sad";
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 0;
	cin >> t;
	while (t--) {
		cin >> n;

		cvs = vector<pair<int, int>>(n, { 0,0 });
		visit = vector<bool>(n, false);

		cin >> start_y >> start_x;

		for (i = 0; i < n; ++i) {
			cin >> cvs[i].first >> cvs[i].second;
		}
		cin >> rock.first >> rock.second;
		Move();
		cout << "\n";
	}
}