[BOJ 16236] 아기 상어

문제

아기 상어

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

 

 

풀이

설명

아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 구하는 문제입니다.

 

규칙은 다음과 같습니다.

• 아기 상어의 처음 크기는 2이고, 1초에 상하좌우로 인접한 한 칸씩 이동 가능합니다.
• 자신보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있습니다.
• 이동한 칸에 자신보다 크기가 작은 물고기가 있다면 먹을 수 있습니다. 물고기를 먹으면 그 칸은 빈 칸이 됩니다.
• 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가합니다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 됩니다.

 

이동 우선순위는 다음과 같습니다.

1. 가장 가까운 물고기
2. 가장 위에 있는 물고기
3. 가장 왼쪽에 있는 물고기

 

BFS을 이용해 해결할 수 있습니다. 추가로 이동 우선순위가 있기 때문에 우선순위 큐를 사용해줍니다.

 

물고기를 잡아먹을 수 없을 때까지 탐색을 반복합니다. 물고기를 잡아 먹은 위치에서 새로 탐색하고, 잡아먹는데 걸린 시간을 더해주면 됩니다.

 

예시 코드

function solution() {
  const N = Number(input());
  const board = Array.from(Array(N), () => input().split(" ").map(Number));
  const shark = { size: 2, eat: 0, x: 0, y: 0, time: 0 };
  const dx = [-1, 0, 0, 1];
  const dy = [0, -1, 1, 0];
  const visited = Array.from(Array(N), () => Array(N).fill(false));

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] === 9) {
        shark.x = i;
        shark.y = j;
        board[i][j] = 0;
        break;
      }
    }
  }

  while (true) {
    const fish = bfs();
    if (!fish) break;

    moveShark(fish);
  }

  return shark.time;

  function bfs() {
    const queue = new PriorityQueue();

    for (let i = 0; i < N; i++) {
      visited[i].fill(false);
    }
    visited[shark.x][shark.y] = true;
    queue.enqueue([shark.x, shark.y, 0]);

    while (!queue.isEmpty()) {
      const [x, y, time] = queue.dequeue();
      if (board[x][y] > 0 && board[x][y] < shark.size) return [x, y, time];

      for (let i = 0; i < 4; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];

        if (!isValidMove(nx, ny)) continue;

        visited[nx][ny] = true;
        queue.enqueue([nx, ny, time + 1]);
      }
    }

    return null;
  }

  function isValidMove(x, y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    if (visited[x][y]) return false;
    if (board[x][y] > shark.size) return false;

    return true;
  }

  function moveShark([x, y, time]) {
    shark.eat++;
    if (shark.eat === shark.size) {
      shark.size++;
      shark.eat = 0;
    }

    board[x][y] = 0;
    shark.x = x;
    shark.y = y;
    shark.time += time;
  }
}