[백준][구현] 16236 아기 상어 NodeJs구현

목차

https://www.acmicpc.net/problem/16236

문제

 

 

문제 구현 방향

중간에 bfs를 가지치기를 통해 효율적으로 하고 싶었는데 안해도 시간초과가 나지 않아 금방 풀렸다.

다 풀었는데 sort 만드는 것을 잘못해서 헤멨다..

 

 

 

정렬 기억하기

// 내림차순 정렬
sort((a, b) => b.y - a.y)

// 오름차순 정렬
sort((a, b) => a.y - b.y)

// y에 대해 우선 정렬 같다면 x에 대해 정렬
//주의 return 안쓰면 틀림
target.sort((a, b) => {
  if (a.y !== b.y) return b.y - a.y;
  else return b.x - a.x;
});

 

. 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let dx = [0, 0, 1, -1];
let dy = [1, -1, 0, 0];
let arr = Array.from(Array(21), () => Array(20).fill(0));
let N = Number(input[0]);

let curpos;
let res = 0;
let cursize = 2;
let eat = 0;
let ts = 0;
for (let i = 1; i <= N; i++) {
  let ar = input[i].trim().split(" ").map(Number);
  for (let j = 0; j < N; j++) {
    if (ar[j] !== 0 && ar[j] !== 9) res++;
    if (ar[j] === 9) {
      curpos = { x: j, y: i - 1 };
    } else arr[i - 1][j] = ar[j];
  }
}
let target = [];

function bfs(strx, stry) {
  let visit = Array.from(Array(21), () => Array(20).fill(0));
  let queue = [];
  visit[stry][strx] = 1;
  queue.push({ x: strx, y: stry });
  while (queue.length) {
    let { x, y } = queue.shift();
    for (let i = 0; i < 4; i++) {
      let nx = x + dx[i];
      let ny = y + dy[i];
      if (nx > N - 1 || nx < 0 || ny > N - 1 || ny < 0) continue;
      if (visit[ny][nx]) continue;
      if (cursize < arr[ny][nx]) continue;
      queue.push({ x: nx, y: ny });
      visit[ny][nx] = visit[y][x] + 1;
      if (arr[ny][nx] < cursize && arr[ny][nx] != 0) {
        if (target.length && target[0].d < visit[ny][nx] - 1) {
          continue;
        }
        target.push({ x: nx, y: ny, sz: arr[ny][nx], d: visit[ny][nx] - 1 });
      }
    }
  }
}

while (1) {
  bfs(curpos.x, curpos.y);
  if (target.length === 0 || res === 0) break;
  target.sort((a, b) => {
    if (a.y !== b.y) return a.y - b.y;
    else return a.x - b.x;
  });

  t = target[0];
  curpos = { x: t.x, y: t.y };
  eat++;
  res--;
  ts += t.d;
  if (eat === cursize) {
    eat = 0;
    cursize++;
  }
  arr[t.y][t.x] = 0;
  target = [];
}
console.log(ts);