[백준 16236 - Node.js] 아기 상어

🔗 문제 링크

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

16236번: 아기 상어

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
const water = input.map(v => v.split(' ').map(Number));
const fishCount = [];
let babySharkPos;
water.forEach((row, x) => row.forEach((size, y) => {
  if (size > 0 && size < 9) {
    fishCount[size] = (fishCount[size] ?? 0) + 1;
  } else if (size === 9) {
    babySharkPos = [x, y];
    water[x][y] = 0;
  }
}));

const offset = [[-1, 0], [0, -1], [0, 1], [1, 0]];
let babySharkSize = 2;
let eaten = 0;
const bfs = (size) => {
  const visited = [...Array(N)].map(() => Array(N).fill(false));
  const [defaultX, defaultY] = babySharkPos;
  visited[defaultX][defaultY] = true;
  let queue = [[defaultX, defaultY, 0]];
  let depth = 0;
  let nextPos;
  while (queue.length) {
    stack = queue;
    queue = [];
    while (stack.length) {
      const [ x, y, elapsed ] = stack.pop();
  
      if (water[x][y] && water[x][y] <= size) {
        if (!depth) {
          depth = elapsed;
          nextPos = [x, y];
        } else {
          const [nx, ny] = nextPos;
          if (nx === x) {
            nextPos = ny < y ? nextPos : [x, y];
          } else {
            nextPos = nx < x ? nextPos : [x, y];
          }
        }
      }
  
      for (let i = 0; i < 4; i++) {
        const nx = x + offset[i][0];
        const ny = y + offset[i][1];
        if (nx >= 0 && nx < N && ny >= 0 && ny < N
          && !visited[nx][ny]
          && water[nx][ny] <= babySharkSize) {
          visited[nx][ny] = true;
          queue.push([nx, ny, elapsed + 1]);
        }
      }
    }
    if (depth) {
      break;
    }
  }

  if (nextPos) {
    const [nx, ny] = nextPos;
    fishCount[water[nx][ny]]--;
    water[nx][ny] = 0;
    babySharkPos = [nx, ny];
    eaten++;
    if (eaten === babySharkSize) {
      eaten = 0;
      babySharkSize++;
      edibleMaxSize++;
    }
  }
  
  return depth;
};

let time = 0;
let edibleMaxSize = 1;
while (fishCount.some((v, i) => i <= edibleMaxSize && v > 0)) {
  const elapsed = bfs(edibleMaxSize);
  if (elapsed) {
    time += elapsed;
  } else {
    break;
  }
}

console.log(time);

먼저 fishCount에 각 크기별 물고기의 개수를 담는다.

아기 상어의 첫 위치의 9는 추후에 물고기 크기를 비교할 때 잘못된 비교를 할 수 있으므로 0으로 변경한다.

처음 상어의 크기는 babySharkSize에 2를, 먹은 물고기 수는 eaten에 0을,

그리고 맨 처음에 먹을 수 있는 물고기의 최대 크기는 1이므로, edibleMaxSize에 이를 저장한다.

 

edibleMaxSize 크기 이하의 물고기들이 존재하는 동안 BFS를 반복한다.

이 때, BFS의 결과로 물고기를 하나 먹고, 먹기까지 경과된 시간을 반환한다.

여기서 경과된 시간들의 누적을 구하면 정답을 구할 수 있다.

만약 BFS의 결과로 0이 반환되었다면 물고기를 먹을 수 없는 상황(아기상어보다 큰 물고기들에 의해 갇힌 상황)이므로 반복을 중지하도록 하였다. 이 부분을 고려하지 않는다면 무한 루프에 빠져 시간 초과가 나게 된다.

 

이제 BFS에서 올바른 순서로 물고기를 찾아 먹고 관련 변수들을 갱신시켜주면 된다.

 

처음에는 문제에서 주어진 먹이를 먹는 순서를 상, 좌, 우, 하 순서로 4방향을 탐색하는 것으로 구현하였다. 그렇게 해서 처음으로 먹을 수 있는 크기의 물고기가 탐색되면 먹고 탐색을 종료시키도록 하였다. 그러나 이는 올바른 순서로 먹이를 먹는 것을 보장하지 못하여 테스트 케이스 4번에서 실패하였다. 테스트 케이스 4번에서 원래 정답이 60인데 56이 나온다면 이 부분 때문일 것이다.

 

올바른 순서로 먹이를 먹도록 하려면 먼저 BFS를 통해 최단 거리의 먹을 수 있는 물고기를 하나 찾은 후, 그 물고기와 동일한 depth에 있는 다른 노드들 중에서 먹을 수 있는 물고기들 중 주어진 조건에 맞는 가장 먼저 먹어야 할 물고기를 가려내야 한다. 즉, 단순히 상, 좌, 우, 하 순서로 4방향 탐색으로는 올바른 순서로 먹이를 먹을 수 없고, 최단 거리 내에 있는 모든 가능성 있는 물고기들을 다 추려내고 그 다음에 어떤 물고기를 먹을지 따져야 한다.

 

예를 들어 BFS를 하는 도중 처음으로 먹을 수 있는 물고기가 있는 칸을 발견하면 그 칸과 동일한 depth에 있는 노드들까지만 탐색을 하고 나머지는 더 이상 보지 않는다. depth가 3인 칸에서 먹을 수 있는 물고기를 최초로 발견했다면, depth가 4 이상인 노드들은 아예 탐색을 하지 않고, depth가 3인 노드들이 현재 stack에 들어와 있으므로 이 stack까지만 탐색을 하고 여기서 조건에 맞는 물고기를 찾아내면 된다.

 

동일한 거리에 있는 먹을 수 있는 물고기 중에서 어떤 물고기를 먹어야 하는지는 x좌표, y좌표 순으로 비교하여 더 작은 쪽 좌표의 물고기를 먹도록 하면 된다.

 

최종적으로 먹을 수 있는 물고기를 하나 선정하고, 그 물고기 크기에 해당하는 fishCount를 갱신하고, 해당 칸을 0으로 갱신한다. 그리고 아기상어의 위치(babySharkPos)를 변경하고, 먹은 물고기 개수(eaten)를 1 증가시킨다. 이 때, 만약 먹은 물고기 개수가 아기상어의 크기(babySharkSize)와 같다면 먹은 물고기 개수를 0으로 초기화하고 아기상어의 크기와 edibleMaxSize를 1씩 증가시킨다.