문제

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

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

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

입력

첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다.

출력

첫째 줄에 안전 거리의 최댓값을 출력한다.

예제 입력

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

예제 출력

2

내가 했던 풀이 방법

1. 8가지 방향을 direction에 저장한다.
2. safe 배열을 N×M 크기로 하고 Infinity로 채워준다.
3. 아기 상어가 있는 위치를 queue에 추가하고, 해당 위치의 safe 값을 0으로 한다.
4. queue의 요소가 없어질 때까지 맨 앞의 요소를 가져오고 해당 위치를 direction 배열을 이용해 이동시킨다. 이때, index가 배열을 벗어나지 않고 safe[nx][ny]가 safe[x][y]+1보다 크다면 현재 값이 더 효율적이므로, safe[nx][ny] 값을 변경해준다. 그리고 queue에 [nx, ny]를 추가해준다.
5. 모든 연산이 끝난 뒤, safe에 존재하는 값 중 가장 큰 값을 출력한다. (safe가 2차원 배열이므로, 1차원 배열로 바꿔주기 위해 flat 메소드를 사용한다.)

코드

const fs = require('fs');
let [n, ...space] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let M = Number(n.trim().split(' ')[1]);

for (let i = 0; i < N; i++) {
  space[i] = space[i].trim().split(' ').map(Number);
}

const direction = [
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
  [1, 1],
];

let safe = Array.from({ length: N }, () => Array(M).fill(Infinity));
let queue = [];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (space[i][j] === 1) {
      queue.push([i, j]);
      safe[i][j] = 0;
    }
  }
}

while (queue.length) {
  let [x, y] = queue.shift();

  for (let i = 0; i < direction.length; i++) {
    let nx = x + direction[i][0];
    let ny = y + direction[i][1];

    if (nx >= 0 && nx < N && ny >= 0 && ny < M && safe[nx][ny] > safe[x][y] + 1) {
      safe[nx][ny] = safe[x][y] + 1;
      queue.push([nx, ny]);
    }
  }
}

console.log(Math.max(...safe.flat()));

회고

BFS가 왜이리 쉽게 안 떠오르는지 모르겠다... BFS 문제를 반복해서 풀어서 적응하도록 해야 할 것 같다.