[백준] 2412 암벽 등반 node/javascript(자바스크립트)

(블로그로 정리된 자료가 없어서 문제 푸는 분들에게 도움이 될까 남겨봅니닷)

 

문제 링크 : https://www.acmicpc.net/problem/2412

풀이 및 사고

좌표를 받아서 y값, x값 순으로 정렬했다. 그리고 좌표가 정렬된 배열에서 index를 가지고 bfs를 돌렸다. y값 차이가 2초과면 멈추게 했다. 그리고 올라가기만 한다는 보장이 없어서 해당 index보다 앞과 뒤 둘 다 탐색했다.

방문 처리는 좌표가 정렬된 배열과 같은 길이의 1차원 배열로 처리했다.

 

(처음에는 전체 board를 저장하는 2차원 배열을 만드려고 했다가 x좌표가 1,000,000이고 y좌표가 200,000인데 메모리 제한이 128MB라 공간 복잡도 초과가 떴다.)

코드

const input = require('fs').readFileSync(process.platform === "linux" ? "/dev/stdin" : "./sample.txt").toString().trim().split("\\n");

const [n, T] = input[0].split(" ").map(Number);
const notMarked = [...Array(n + 1)].map(() => true);
const arr = [[0, 0]];

for (let i = 1; i < n + 1; i++) {
  let [x, y] = input[i].split(" ").map(Number);
  arr.push([x, y]);
}

arr.sort((a, b) => a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]);

(() => {
  const queue = [0];
  let cnt = 0;
  notMarked[0] = false;

  while (queue.length > 0) {
    let l = queue.length;
    cnt += 1;
    for (let i = 0; i < l; i++) {
      const curIdx = queue.shift();
      const [x, y] = arr[curIdx];
      let preStop, postStop;

      for (let di = 1; di < n + 1; di++) {
        let preIdx = curIdx - di;
        let postIdx = curIdx + di;
        preStop = true;
        postStop = true;
        //forward
        if (preIdx >= 0 && Math.abs(y - arr[preIdx][1]) <= 2) {
          preStop = false;
          if (Math.abs(x - arr[preIdx][0]) <= 2) {
            if (arr[preIdx][1] === T) {
              console.log(cnt);
              return;
            }
            if (notMarked[preIdx]) {
              notMarked[preIdx] = false;
              queue.push(preIdx);
            }
          }
        }
        //backward
        if (postIdx < n + 1 && Math.abs(y - arr[postIdx][1]) <= 2) {
          postStop = false;
          if (Math.abs(x - arr[postIdx][0]) <= 2) {
            if (arr[postIdx][1] === T) {
              console.log(cnt);
              return;
            }
            if (notMarked[postIdx]) {
              notMarked[postIdx] = false;
              queue.push(postIdx);
            }
          }
        }

        if (preStop && postStop) { break; }

      }
    }
  }
  console.log(-1);
})();

느낀점

탐색 문제는 피지컬 문제라고 생각하는데 js로 푸는 피지컬이 많이 부족하다고 느꼈다. 중간중간 오류도 많이 나고 특히 queue길이로 for문을 돌릴때 조건에 queue.length로 넣게 되면 내부 코드가 돌면서 바뀌는 queue 길이가 반영된다는 걸 찾았다. 그래서 l 변수로 길이를 받아서 사용했는데 이런 사소한 문제들이 코테볼때 발생하지 않도록 많이 풀어야겠다.