[백준] 17086 아기 상어2 Node.js (BFS 풀이)

문제

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

2

예제 입력 2

7 4
0 0 0 1
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
0 1 0 0
0 0 0 1

예제 출력 2

2

---

문제풀이

💡 문제풀이 과정

• 처음에 문제를 풀 때는 상어가 없는 칸을 시작 위치로 BFS를 실행했는데, 다른 풀이를 참고하니 상어가 있는 칸에서부터 탐색을 시작하는 것이 더 효율적이었다.

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input.shift().split(' ').map(Number);
const graph = input.map((v) => v.split(' ').map(Number));
const dx = [1, -1, 0, 0, 1, -1, -1, 1]; // 인접한 x좌표
const dy = [0, 0, 1, -1, 1, -1, 1, -1]; // 인접한 y좌표

const queue = [];
const bfs = () => {
  while (queue.length) {
    const [x, y] = queue.shift();

	// 현재 위치에서 인접한 여덟 방향 탐색을 위한 반복문
    for (let i = 0; i < 8; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

	  // 해당 위치가 그래프의 범위를 벗어났거나 상어가 있는 칸이면 패스
      if (nx < 0 || nx >= N || ny < 0 || ny >= M || graph[nx][ny]) continue;

      graph[nx][ny] = graph[x][y] + 1;
      queue.push([nx, ny]);
    }
  }
};

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
	// 상어가 있는 위치 값 큐에 담기
    if (graph[i][j]) queue.push([i, j]);
  }
}

bfs();

// 그래프의 값들 중 최댓값 -1 반환
console.log(Math.max(...graph.flat()) - 1);