문제

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

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

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

입력

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

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

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

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

출력

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

예제

예제 입력 1

2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

예제 출력 1

happy
sad

해결방안

출발지점에서 도착지점까지 갈 수 있는지 없는지를 구해야 하는데 중요한 것은 도착지점까지 가는 도중에 편의점에 들릴지 말지 결정하는 부분이였다고 생각한다. 그래서 나는 다음과 같은 로직을 토대로 구현해봤다.

1. 처음 시작지점에서 도착지점까지 거리가 1000이하 이면 종료(happy출력)
2. 시작지점에서 각각의 편의점까지 거리가 1000인 편의점을 방문처리하고 큐에 넣는다.
3. 큐에서 편의점을 하나 꺼내고 이 편의점에서 갈 수 있는 다음 편의점이 있다면 방문처리 후 큐에 넣는다.
   3-1. 도착지점까지 거리가 1000이하라면 반복문 종료(happy출력)
4. 3번 반복
5. 큐를 탐색하는 동안 도착지점에 도착하지 못했다면 sad출력

배운점

방문처리하는 부분에 대해서 Map 자료구조를 사용했는데 그 이유는 키의 자료형은 string뿐만 다른 자료형도 들어갈 수 있다고 생각해서였다. 하지만 원시타입만 가능할 뿐 참조타입은 안된다는것을 몰랐기에 Map의 키값으로 배열을 넣고 방문처리를 구현할 수 없었다.
[1,2] === [1,2] => false

코드

const [TC, ...input] = `4
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000
0
0 0
500 501
0
0 0
500 499`
  .toString()
  .trim()
  .split("\n");
// console.log(TC, input);
const answer = [];

const distanceBetweenTwoPoints = (x1, y1, x2, y2) => {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};

for (let i = 0; i < input.length; i++) {
  const storeCnt = +input[i++];
  const start = input[i++].split(" ").map(Number);
  const store = [];
  let cnt = 0;
  for (let j = i; j < i + storeCnt; j++) {
    const [x, y] = input[j].split(" ").map(Number);
    store.push([x, y, cnt++]);
  }
  i += storeCnt;
  const end = input[i].split(" ").map(Number);

  //   console.log("편의점 개수 : ", storeCnt);
  //   console.log("출발지점 : ", start);
  //   console.log("편의점 모음 : ", store);
  //   console.log("도착지점 : ", end);

  if (distanceBetweenTwoPoints(start[0], start[1], end[0], end[1]) <= 1000) {
    answer.push("happy");
    continue;
  }

  const visited = new Array(store.length).fill(0);
  const queue = [];
  for (let k = 0; k < store.length; k++) {
    const [storeX, storeY, index] = store[k];

    if (distanceBetweenTwoPoints(start[0], start[1], storeX, storeY) <= 1000) {
      queue.push([storeX, storeY, index]);
      visited[index] = 1;
    }
  }
  //   console.log(queue);
  let idx = 0;
  let flag = 0;
  while (idx < queue.length) {
    const [curR, curC, index] = queue[idx++];

    if (distanceBetweenTwoPoints(curR, curC, end[0], end[1]) <= 1000) {
      answer.push("happy");
      flag = 1;
      break;
    }
    for (let i = 0; i < store.length; i++) {
      const [storeX, storeY, idx] = store[i];

      if (
        distanceBetweenTwoPoints(curR, curC, storeX, storeY) <= 1000 &&
        !visited[idx]
      ) {
        queue.push([storeX, storeY, idx]);
        visited[idx] = 1;
      }
    }
  }
  if (flag) continue;
  answer.push("sad");
}
console.log(answer.join("\n"));