[백준] 9205번: 맥주 마시면서 걸어가기 - Node.js (자바스크립트)

1. 문제 ㅡ 9205번: 맥주 마시면서 걸어가기 (난이도: Gold V)

9205번: 맥주 마시면서 걸어가기

2. 풀이 ㅡ Node.js (자바스크립트)

class Queue {
  constructor(initValue) {
    this.q = initValue ? [initValue] : [];
    this.head = 0;
    this.tail = initValue ? 1 : 0;
  }

  push(item) {
    this.q[this.tail++] = item;
  }

  shift() {
    this.head++;
    return this.q[this.head - 1];
  }

  isEmpty() {
    return this.head === this.tail;
  }
}

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const testCases = (() => {
  const tcs = [];
  let head = -1;
  let N = input.shift();

  while (N--) {
    const stores = [];
    let storeCount = +input[++head];
    const home = input[++head].split(' ').map(val => +val);

    while (storeCount--) {
      stores.push(input[++head].split(' ').map(val => +val));
    }

    const fetival = input[++head].split(' ').map(val => +val);

    tcs.push({ home, storeCount, stores, fetival });
  }

  return tcs;
})();

const isWithinThousand = (x1, y1, x2, y2) => {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2) <= 1000 ? true : false;
};

const isHappy = tc => {
  const { home, storeCount, stores, fetival } = tc;
  const visited = Array.from({ length: storeCount }, () => false);
  const [festivalX, festivalY] = fetival;
  const queue = new Queue(home);

  while (!queue.isEmpty()) {
    const [x, y] = queue.shift();

    if (isWithinThousand(x, y, festivalX, festivalY)) return 'happy';

    stores.forEach((store, idx) => {
      const [storeX, storeY] = store;

      if (visited[idx] || !isWithinThousand(x, y, storeX, storeY)) return;

      queue.push(store);
      visited[idx] = true;
    });
  }

  return 'sad';
};

testCases.forEach(tc => console.log(isHappy(tc)));

2-1. 풀이 설명

50m를 이동할 때마다 맥주 한 병을 마셔야 하고, 맥주는 20병씩 가지고 다닐 수 있다. 즉 상근이는 20 * 50 해서 한 번에 1000m 씩 이동할 수 있는 셈이다. 즉, 상근이가 위치한 곳에서 1000m 이내에 다음 편의점 or 페스티벌이 위치하면 상근이는 행복한 상태를 유지할 수 있다. 

 

상근이의 집 좌표를 queue에 넣고 BFS를 시작한다. 주의해야 할 점은:

 

• 편의점의 좌표는 상근이의 이동경로에 따라 나열되어 있지 않다는 점이다. 즉, 편의점 2 곳의 좌표가 주어졌다고 가정했을 때 두 번째 편의점이 첫 번째 편의점보다 상근이의 위치와 더 가까울 수 있다.
• 혹은, 편의점에 따로 들리지 않고 바로 집에서 페스티벌로 바로 갈 수도 있다 (아래 이미지 참고)

따라서 while문을 돌면서 가장 먼저 페스티벌의 좌표가 현재 확인 중인 좌표에서 1000m 이내면 'happy'를 반환하도록 브레이크 포인트를 잡아준다. 만약 페스티벌이 1000m 이내의 거리에 없다면, 아직 방문하지 않은 편의점 중 현재 상근이의 위치에서 1000m 이내의 거리에 위치한 매장들의 좌표를 queue에 넣어주고 매장 방문여부를 true로 바꿔준다. while문이 정상 종료된 후에는 상근이가 페스티벌까지 맥주를 마시면서 걸어갈 수 없다고 판단해 'sad'를 반환하도록 하면 된다.