[백준2589_자바스크립트(javascript)] - 보물섬

🔴 문제

보물섬

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [rc, ...inputs] = fs.readFileSync(path).toString().trim().split('\n');
const map = inputs.map((it) => it.split(''));
const [r, c] = rc.split(' ').map(Number);
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
let ans = -1;

const bfs = (x, y) => {
  const visited = Array.from({ length: r }, () => Array(c).fill(false));
  const q = [[x, y]];
  let front = 0;

  visited[x][y] = 1;

  while (front < q.length) {
    const [x, y] = q[front++];

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

      if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
      if (map[nx][ny] === 'W') continue;
      if (!visited[nx][ny]) {
        visited[nx][ny] = visited[x][y] + 1;
        ans = Math.max(visited[nx][ny], ans);
        q.push([nx, ny]);
      }
    }
  }
};

for (let i = 0; i < r; i++) {
  for (let j = 0; j < c; j++) {
    if (map[i][j] === 'L') bfs(i, j);
  }
}

console.log(ans - 1);

🟢 풀이

⏰ 소요한 시간 : 15분

모든 육지좌표에서 다른 육지까지의 최단 거리를 구하고, 그 최단거리들 중에 가장 큰 값을 구해주면 되는 문제다.
따라서 중첩반복하면서 맵의 위치가 육지라면 그 육지를 기준으로 BFS를 수행해준다.
육지를 기준으로 다음 육지에 도달했다면 해당 위치까지의 거리와 이전의 최단거리 중 가장 큰값을 비교해 더 큰값으로 업데이트 해주면 된다.

비록 BFS의 기본 유형이긴 하지만... 그래프 공포증이 있는 내가 15분만에 문제를 풀고 맞았습니다를 받았다는 것이 매우 감격적...!!!

🔵 Ref