※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
시작지점에서 임의의 편의점을 경유하여 맥주가 비지 않게 유지하며 도착지점에 도달할 수 있는지를 파악하는 문제입니다.
중요한 것은 어느 경로를 지나가며 도착하는지가 아니라, 도착할 수 있는지, 없는지에 대한 정보 뿐이므로 어느 한 편의점에 도착했다고 하면, 그 편의점은 다른 경로로 도착하는 경우를 파악할 필요가 없게 됩니다.
따라서 BFS 알고리즘을 이용하여, 시작지점에서 갈 수 있는 편의점 목록을 구하고, 그 편의점부터 도착지점에 도착할 수 있는지를 체크하면 되며, 한번 큐에 들어온 편의점은 별도의 boolean 배열 체크를 통해 중복해서 넣어주지 않아도 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
typedef long long ll;
using namespace std;
class Node
{
public:
int x, y, dist;
Node() {}
Node(int x, int y) : x(x), y(y) { dist = x + y; }
bool operator <(const Node &n)
{
return dist < n.dist;
}
};
int n, sx, sy, px, py, ex, ey;
bool calc(Node a, Node b)
{
return (abs(a.x - b.x) + abs(a.y - b.y)) <= 1000;
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--)
{
bool f = false, visited[101] = { 0 };
vector<Node> w;
cin >> n >> sx >> sy;
for (int i = 0; i < n; i++)
{
cin >> px >> py;
w.push_back({ px,py });
}
cin >> ex >> ey;
Node s(sx,sy), e(ex,ey);
if (calc(s, e)) f = true;
queue<int> q;
for (int i = 0; !f && i < n; i++)
{
if (calc(s,w[i]))
{
visited[i] = true;
q.push(i);
}
}
while (!q.empty())
{
int now = q.front();
q.pop();
if (calc(w[now], e))
{
f = true;
break;
}
for (int i = 0; i < n; i++)
{
if (!visited[i] && calc(w[now], w[i]))
{
visited[i] = true;
q.push(i);
}
}
}
cout << (f ? "happy" : "sad") << "\n";
}
}