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

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

코드

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

#define MAX 101
#define CAN_MOVE 1000
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef pair<int, int> pi;
int t, n;
bool visit[MAX];
pi h, f;
vector<pi> store;

bool bfs() {
	queue<pi>q;
	q.push(h);

	while (!q.empty()) {
		int nx = q.front().first;
		int ny = q.front().second;
		q.pop();

		if (abs(f.first - nx) + abs(f.second - ny) <= CAN_MOVE)
			return true;

		for (int i = 0; i < n; i++) {
			if (visit[i]) continue;
			if (abs(store[i].first - nx) + abs(store[i].second - ny) <= CAN_MOVE) {
				visit[i] = true;
				q.push(store[i]);
			}
		}
	}
	return false;
}

int main() {
	FASTIO;
	cin >> t;
	while (t--) {
		cin >> n;
		store.resize(n);
		cin >> h.first >> h.second;

		for (int i = 0; i < n; i++) {
			cin >> store[i].first >> store[i].second;
		}

		cin >> f.first >> f.second;

		if (bfs()) cout << "happy\n";
		else cout << "sad\n";
		memset(visit, false, sizeof(visit));
	}
	return 0;
}

설명

처음에는 상근이의 집에서 시작하고, 편의점을 방문하면서 페스티벌 장소까지 맥주를 마시며 갈 수 있는지 확인하는 문제입니다. BFS를 통해 문제를 해결할 수 있습니다.

 

먼저 큐에는 상근이의 현재 위치를 넣어줍니다. 거리는 맨해튼 거리이기 때문에 X 좌표와 Y 좌표의 차이를 이용하고, 50미터 당 맥주 한 병을 마실 수 있으므로 집 혹은 편의점을 나서면 1000미터까지 이동할 수 있습니다. 현재 위치에서 1000미터 내에 페스티벌 장소가 있으면 바로 true를 리턴하고, 그렇지 않으면 방문하지 않은 편의점에 대해서 위치 상 방문 가능한지 확인합니다. 방문이 가능하면 다시 맥주를 구매할 수 있으므로 큐에 넣어줍니다.

 

return 값에 따라 happy 혹은 sad를 출력합니다.

 

느낀 점

평소에 풀던 bfs와 약간 다른 느낌이라 새로웠습니다.