맥주 마시면서 걸어가기

문제 설명

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

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

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

입력

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

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

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

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

출력

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

문제 풀이(실패)

1. 테스트 케이스를 인풋값에서 추출.
2. 각 테스트 케이스에 대해서 for문.
   1. convenience에 destination을 넣어줌.
   2. queue를 만들고 currentLocation을 시작점으로 설정.
      1. queue가 0이 될떄까지 while.
      2. destination의 x,y 값이랑 같으면 happy를 출력.
      3. convenience의 길이가 i랑 같을때까지 while.
         1. 거리를 구해서 거리가 1000보다 작거나 같으면 queue에 push.
         2. 그렇지 않으면 i를 증가시킴.
      4. happy를 출력하지 못하고 queue의 길이가 0이되면, sad를 출력.

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

const testCaseCount = Number(input[0].trim());

const getTestCases = (inputs, testCaseCount) => {
  const cases = [];
  let index = 0;
  for (let count = 0; count < testCaseCount; count++) {
    const convenienceCount = Number(inputs[index].trim());
    let tempIndex = index;
    index += convenienceCount + 2 + 1;
    const testCase = {
      currentLocation: null,
      destination: null,
      convenience: [],
    };
    for (let location = tempIndex + 1; location < index; location++) {
      if (location === tempIndex + 1)
        testCase.currentLocation = inputs[location]
          .trim()
          .split(" ")
          .map(element => Number(element));
      else if (location === index - 1)
        testCase.destination = inputs[index - 1]
          .trim()
          .split(" ")
          .map(element => Number(element));
      else {
        testCase.convenience.push(
          inputs[location]
            .trim()
            .split(" ")
            .map(element => Number(element))
        );
      }
    }
    cases.push(testCase);
  }
  return cases;
};

const testCases = getTestCases(input.slice(1, input.length), testCaseCount);

const executeBFS = () => {
  testCases.forEach(testCase => {
    const { currentLocation, destination } = testCase;
    let convenience = testCase.convenience;
    const [endX, endY] = destination;
    convenience.push(destination);
    const queue = [currentLocation];
    while (queue.length) {
      const [startX, startY] = queue.shift();
      if (endX === startX && endY === startY) {
        console.log("happy");
        return;
      }

      let i = 0;
      while (i !== convenience.length) {
        const [nx, ny] = [
          Math.abs(startX - convenience[i][0]),
          Math.abs(startY - convenience[i][1]),
        ];
        if (nx + ny <= 1000) {
          queue.push([convenience[i][0], convenience[i][1]]);
          convenience = convenience.filter((_, id) => id !== i);
          i = 0;
          break;
        } else {
          i++;
        }
      }
    }
    console.log("sad");
  });
};

executeBFS();

틀린 이유 찾는중.

7/27 왜 틀린지 잘 모르겠다. 어딘가 확실하게 틀렸으니 안돌아가는거 같은데,
bfs나 dfs말고 플로이드 와샬 알고리즘을 적용해서 풀어보는게 좋을 것 같다.

다음에 도전해봐야겠다.

8/1 틀린 부분 못찾겠어가지고 플로이드와샬알고리즘을 이용해서 풀었다. 어려웠다..

문제풀이

1. 테스트케이스에서 각 정점들 추출.
2. 정점의 크기만큼 edge를 표현해줄수 있는 2차원 배열 선언.
3. 정점을 돌면서 연결이 가능하면 1로 표시(가중치는 중요하지 않음.)
4. 플로이드 와샬 알고리즘을 통해서 집에서 페스티발까지 도달할 수 있으면 infinity값이 아니여야함.

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

const testCaseCount = Number(input[0].trim());

const transformStrToArr = (str, splitOption = " ") => {
  return str
    .trim()
    .split(splitOption)
    .map(element => Number(element));
};

const getTestCases = (inputs, testCaseCount) => {
  const cases = [];
  let index = 0;
  for (let count = 0; count < testCaseCount; count++) {
    const convenienceCount = Number(inputs[index].trim());
    let tempIndex = index;
    index += convenienceCount + 2 + 1;
    const testCase = {
      vertex: [],
    };
    for (let location = tempIndex + 1; location < index; location++) {
      testCase.vertex.push([...transformStrToArr(inputs[location])]);
    }
    cases.push(testCase);
  }
  return cases;
};

const testCases = getTestCases(input.slice(1, input.length), testCaseCount);

const make2Arr = testCase => {
  const { vertex } = testCase;
  const n = vertex.length;
  const connected = Array.from(Array(n), () => Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const [x, y] = vertex[i];
      const [x2, y2] = vertex[j];
      const distance = Math.abs(x - x2) + Math.abs(y - y2);
      if (distance <= 1000) {
        connected[i][j] = 1;
      }
    }
  }
  return connected;
};

testCases.forEach(testCase => {
  const connected = make2Arr(testCase);
  const n = connected.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (connected[i][j] > connected[i][k] + connected[k][j]) {
          connected[i][j] = connected[i][k] + connected[k][j];
        }
      }
    }
  }
  connected[0][n - 1] !== Infinity ? console.log("happy") : console.log("sad");
});