출처:https://www.acmicpc.net/problem/9205
BFS를 떠올리기 생각보다 쉽지 않은 문제이다. 이걸보고 바로 BFS라고 떠올렸다면 바로 풀면 되지만, 그래프 탐색쪽으로 가서, 여러가지 경우를 생각하는 순간 생각의 늪에 빠질 수 있다.
여기서 핵심은 , 편의점에서 맥주를 리필할 수 있다는 건데, BFS를 이용하면 상근이와 친구들이 해당 지점에서 갈 수 있는 모든 편의점을 일단 가본 상태에서 또 모든 지점을 가보기 때문에, "도착할 수 있냐" ,"도착할 수 없냐"의 판단을 할 수 있게 된다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define X first
#define Y second
using namespace std;
vector<pair<int, int>> store;
pair<int, int> start;
pair<int, int> festival;
bool visited[100];
void trace()
{
queue<pair<int, int>> Q;
Q.push({start.X, start.Y});
while (!Q.empty())
{
pair<int, int> cur = Q.front();
Q.pop();
if (abs(festival.X - cur.X) + abs(festival.Y - cur.Y) <= 1000)
{
cout << "happy" << '\n';
return;
}
for (int i = 0; i < store.size(); i++)
{
int nx = store[i].X;
int ny = store[i].Y;
// 못가는 편의점은 넘어가기.
if (abs(nx - cur.X) + abs(ny - cur.Y) > 1000)
continue;
// 이미 방문한 편의점은 방문할 필요없다.
if (visited[i])
continue;
visited[i] = true;
Q.push({nx, ny});
}
}
// 다 했는데도, return을 못만난다면 못가는거임.
cout << "sad" << '\n';
return;
}
int main()
{
fastio;
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
// 전역 변수이기 때문에, 초기화가 필요하다.
fill(visited, visited + N, false);
store.clear();
cin >> start.X >> start.Y;
int x, y;
for (int i = 0; i < N; i++)
{
cin >> x >> y;
store.push_back({x, y});
}
cin >> festival.X >> festival.Y;
trace();
}
return 0;
}