BOJ (C/C++) 9205번: 맥주 마시며 걸어가기

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

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

---

풀이

편의점에 들를 땐 최대 20병씩 맥주를 채울 수 있음 >> 거리가 1000m 이하일 경우 도달할 수 있음한 번 방문하여 큐에 삽입된 지점은 다시 가지 않음>> 이 부분이 잘 이해가 안 갔는데 1-2의 루트가 있고 1-3-2의 루트가 있으면 1-3-2는 1-2에 포함되므로 안 따져도 되는 듯??이 문제는 루트를 찾는 것이 아닌 갈 수 있는지의 여부만을 물어보는 문제라 이 부분은 안 따져도 될 것 같음또한 큐에 삽입된 지점만 재방문이 안 되므로 괜찮은 것 같음(아니라면 댓글로 알려주세요ㅠ)

---

코드

#include <stdio.h>
#include <queue>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

vector <pair<int, int>> V;
bool visited[105];
int fx, fy;

bool Beer(int sx, int sy, int n) {
	queue <pair<int, int>> Q;
	int x, y;

	// 큐에 시작 지점 삽입
	Q.push({ sx,sy });

	while (!Q.empty()) {
		x = Q.front().first, y = Q.front().second;
		Q.pop();

		// 현재 지점에서 페스티벌 지점에 도달 가능하면 true 리턴
		if (abs(fx - x) + abs(fy - y) <= 1000) return true;

		for (int i = 0; i < n; i++) {

			// 방문했던 지점일 경우 다시 탐색 X
			if (visited[i]) continue;

			// 다음 지점까지의 거리 계산 후 갈 수 있는 곳이라면 큐에 삽입하여 탐색
			int len = abs(V[i].first - x) + abs(V[i].second - y);
			if (len <= 1000) {
				Q.push({ V[i].first, V[i].second });
				visited[i] = true;
			}
		}
	}
	return false;
}

int main() {
	int t, n, hx, hy, x, y;
	
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {

		// input
		scanf("%d", &n);
		scanf("%d %d", &hx, &hy);

		for (int j = 0; j < n; j++) {
			scanf("%d %d", &x, &y);
			V.push_back({ x,y });
		}

		scanf("%d %d", &fx, &fy);

		// 리턴 값이 true면 happy
		if (Beer(hx, hy, n)) printf("happy\n");
		else printf("sad\n");

		// init
		V.clear();
		fill(visited, visited + n, false);
	}
	return 0;
}