백준 16236 < 아기 상어 > JavaScript

📍문제 링크

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

16236번: 아기 상어

 

📍알고리즘 분류

- 구현
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 시뮬레이션

 

📍문제 풀이

2차원 배열이 주어지고 상어와 1 ~ 6 크기의 물고기들이 2차원 배열에 위치할 때, 상어가 먹을 수 있는 모든 물고기를 잡아먹는데 걸리는 시간을 구한다

 

1. 먹을 수 있는 물고기들 좌표를 모두 조사한다

- BFS를 이용한다

- 먹을 수 있는 물고기가 더 이상 없으면, 진행을 멈추고 시간을 출력한다

 

2. 먹을 수 있는 물고기 좌표 배열에서 가장 가깝고, 위에 있고, 왼쪽에 있는 좌표를 구한다

- 1번에서 조사한 좌표들 리스트를 sort() 함수로 정렬한다

- 비교 콜백 함수를 통해 우선순위를 부여한다

 

3. 좌표로 상어를 이동시킨다

- 현재 크기만큼 물고기를 잡아먹었으면, 크기를 1 늘리고, 다시 잡아먹어야할 물고기를 현재 크기로 일치시킨다

- 이동한 거리를 계산해서 더해준다

 

BFS 함수를 만들 때, 방문 여부도 확인하고, 이동 거리도 실시간으로 업데이트해줘야 한다

- 방문 여부를 체크할 이차원 배열을 전부 0으로 초기화하고, 시작지점부터 +1씩 늘려가주면 거리 업데이트와 방문 체크를 한 번에 할 수 있다 (0이면 미방문, 1 이상이면 방문)

- 첫 시작 지점을 1부터 시작했으니, 마지막에 -1 해주면 된다

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];

const getFirstSharkPos = (N, Board) => {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (Board[i][j] === 9) return [i, j];
    }
  }
};

// bfs로 먹을 수 있는 모든 물고기의 좌표와 이동 거리를 배열로 반환하는 함수
const getEdibleFishArr = (SharkPos, Size, N, Board) => {
  const result = [];
  const queue = [SharkPos];
  // 0 이면 미방문
  const isVisited = Array.from({ length: N }, (_) =>
    Array.from({ length: N }, (_) => 0),
  );
  // 시작 위치를 1로 하여 1 이상이면 방문으로 체크
  isVisited[SharkPos[0]][SharkPos[1]] = 1; // 마지막에 1 빼주면 됨
  while (queue.length) {
    const [Y, X] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const [newY, newX] = [Y + dy[i], X + dx[i]];
      if (
        newY >= 0 &&
        newX >= 0 &&
        newY < N &&
        newX < N &&
        !isVisited[newY][newX] &&
        Board[newY][newX] <= Size
      ) {
        queue.push([newY, newX]);
        isVisited[newY][newX] = isVisited[Y][X] + 1;
        if (Board[newY][newX] && Board[newY][newX] < Size) {
          result.push([isVisited[newY][newX] - 1, newY, newX]);
        }
      }
    }
  }
  // 거리가 가깝고, 위에 있고, 왼쪽에 있는 순으로 이동 가능한 좌표를 정렬
  return result.sort((a, b) => {
    if (b[0] === a[0]) {
      if (b[1] === a[1]) return b[2] - a[2];
      return b[1] - a[1];
    }
    return b[0] - a[0];
  });
};

// needFishes 가 0일 경우 호출
const sizeUp = (Size) => {
  return [Size + 1, Size + 1]; // 새 사이즈와 needFishes를 반환
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const N = +input.shift();
  const board = input.map((row) => row.split(" ").map(Number));
  let sharkPos = getFirstSharkPos(N, board);

  let size = 2; // 현재 사이즈
  let needFishes = size; // 레벨업에 필요한 물고기 갯수
  let seconds = 0;

  while (true) {
    const edibleFishArr = getEdibleFishArr(sharkPos, size, N, board);
    if (!edibleFishArr.length) break;
    const [distance, sharkY, sharkX] = edibleFishArr[edibleFishArr.length - 1];
    seconds += distance;
    // 원래 상어 위치를 0으로
    board[sharkPos[0]][sharkPos[1]] = 0;
    // 새로운 상어 위치 업데이트
    board[sharkY][sharkX] = 9;
    sharkPos = [sharkY, sharkX];
    needFishes -= 1;
    // 레벨업
    if (needFishes === 0) {
      [size, needFishes] = sizeUp(size);
    }
  }
  console.log(seconds);
});