문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.

어떻게 풀까?

상근이의 집에서 중간 중간 편의점을 들르면서 펜타포트 락 페스티벌 까지도착해야하는 문제다.
상근이의 집을 s, 페스티벌을 e, 편의점을 m1, m2 ... 라고 할 때
s -> m1 -> m2 -> ... -> e 경로를 잘 짜야하는 문제다.
맥주당 50미터고 총 20개를 들 수 있으니 맨해튼 거리로 한번에 1000미터를 이동할 수 있다.
즉 각 정점마다 거리가 1000 이하가 되는 경로를 찾으면 happy, 못찾으면 sad를 출력하면 될것같다.

모든 편의점을 지날 필요는 없고, 경로를 출력하는게 아닌 도착하는지 여부만 파악하면 되므로
s에서 bfs 알고리즘으로 탐색을 시작해 만나는 정점(m 또는 e) 을 큐에 넣고, 큐가 빌 때 까지 bfs를 시행하고 e가 큐에서 나오는지 확인해주면 되는것으로 보인다.

좌표평면의 크기가 65536 * 65536 이므로 이중벡터로 표현하는건 메모리초과에 걸릴것 같아서
각 정점마다 간선이 있다고 가정하고 간선의 가중치를 맨해튼 거리로 표현하기로 한다.
간선의 가중치가 1000을 넘기면 간선을 삭제하는 과정을 추가하고 이 그래프에서 bfs를 시행해서 s에서 e로 가는 경로가 나오면 "happy"를, 나오지 않으면 "sad"를 출력하는것으로 방향을 정했다.

그래프의 저장은 각 정점에 번호를 부여하고 인접행렬로 표현할 생각이다.
정점의 개수는 최대 102개이므로(시작, 중간 100개, 끝) 102 * 102 크기의 이중벡터를 선언하고
시작점을 0번 중간번호를 1~n-2 끝지점을 n-1번으로 지정하고
각 정점끼리 연결되어있으면 1 연결되어있지 않으면 0으로 표현한다.
연결여부는 정점끼리 맨해튼 거리가 1000이하인지 초과인지를 기준으로 한다.

문제에서 그래프 정보를 주는것이 아니니 각 정점의 좌표를 저장하는

vector<pair<int, int>> v;

벡터에 저장하고, 이중 반복문으로 각 정점마다 맨해튼 거리를 계산해서 인접행렬에 표현하면 될것같다.

고민한 부분

각 좌표를 이중벡터로 표현하면 너무 메모리가 커질것 같았다.
찾아본 결과 1억 바이트는 대략 100메가 정도인것을 알았고 int형 이중벡터는 5000 * 5000까지 한계인것으로 생각하면 될것같다.
메모리 초과를 어떻게 피할지가 고민한 부분이었고, 모든 정점을 좌표에 찍는게 아닌 좌표끼리의 관계로 그래프를 그리는 방법으로 메모리를 줄였다.