[BOJ] 맥주 마시면서 걸어가기(C++)

풀이 소요시간 : 20분

BFS 를 사용해서 풀 수 있는 문제였다. 굳이 좌표를 도입하지 않고 Vector 를 사용하여 편의점의 정보를 저장했다. 어떤 편의점에서 어떤 편의점으로 이동했는지 여부를 저장하는 Visit 배열을 사용했고, 이를 위해 편의점을 식별하는 id 값을 부여하여 수월하게 풀이했다.

전체 코드

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

int T, N;
int mx, my;
int gx, gy;

struct Store {
	int id;
	int x;
	int y;
};

vector<Store> Vector;
int Visit[101][101];

void Input() {
	cin >> T;
}

void Clear() {
	Vector.clear();
	for (int i = 0; i < 101; i++)
	{
		for (int j = 0; j < 101; j++)
		{
			Visit[i][j] = 0;
		}
	}
}

void Bfs() {

	queue<pair<pair<int, int>, int>> Q;
	Q.push({ {mx, my}, 0 });
	//원점 = 0, 편의점 = 1 - 100

	while (!Q.empty())
	{
		int px = Q.front().first.first;
		int py = Q.front().first.second;
		int pid = Q.front().second;
		Q.pop();

		if (abs(px - gx) + abs(py - gy) <= 1000)
		{
			cout << "happy" << '\n';
			return;
		}

		for (int i = 0; i < Vector.size(); i++)
		{
			int nid = Vector[i].id;
			int nx = Vector[i].x;
			int ny = Vector[i].y;

			if (abs(px - nx) + abs(py - ny) > 1000) continue;
			if (Visit[pid][nid] == 1) continue;

			Visit[pid][nid] = 1;
			Q.push({ {nx, ny}, nid });
		}
		
	}

	cout << "sad" << '\n';
	return;

}

int main()
{
	Input();
	while (T--)
	{
		cin >> N;
		cin >> mx >> my;
		for (int i = 0; i < N; i++)
		{
			int x, y;
			cin >> x >> y;
			Vector.push_back({ i + 1, x, y });
			// id : 1 - 100
		}

		cin >> gx >> gy;
		Bfs();
		Clear();
	}
}