아기상어2

아기 상어 2

문제 설명

N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.

어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다.

안전 거리가 가장 큰 칸을 구해보자.

예제 입력

5 4
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 1

예제 출력

2

---

문제 풀이

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

const solution = (input) => {
  const dx = [-1, 1, 0, 0, -1, 1, 1, -1];
  const dy = [0, 0, -1, 1, -1, -1, 1, 1];
  const [N, M] = input[0].split(" ").map(Number);
  const arr = input.slice(1).map((line) => line.split(" ").map(Number));

  const bfs = () => {
    let queue = [];
    let head = 0;
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (arr[i][j] === 1) queue.push([i, j]);
      }
    }

    while (queue.length > head) {
      const [x, y] = queue[head++];
      for (let k = 0; k < 8; k++) {
        let nx = x + dx[k];
        let ny = y + dy[k];
        if (0 <= nx && nx < N && 0 <= ny && ny < M) {
          if (arr[nx][ny] === 0) {
            arr[nx][ny] = arr[x][y] + 1;
            queue.push([nx, ny]);
          }
        }
      }
    }
  };

  let mx = 0;
  bfs();

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      mx = Math.max(mx, arr[i][j]);
    }
  }
  console.log(mx - 1);
};
solution(input);

아이디어 / 접근법

1. 반복문을 돌려서 상어의 좌표 다 넣어주기
2. 8방향 델타 탐색 이후 원본 배열 갱신 후 queue에 추가
3. 최댓값 출력

후기

다시 BFS 감을 잡고자 푼 문제인데 별로 어려운 것은 없었고 상어들의 좌표를 다 queue에 넣어놓고 시작해야 한다는 점이 좀 달랐음