[백준] 2589 보물섬 - javascript

📌 문제

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

📌 풀이

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

const [row, col] = input.shift().split(" ").map(Number);

let arr = input.map((i) => i.split(""));

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

function bfs(y, x) {
  const queue = [];
  let visited = Array.from(Array(row), () => Array(col).fill(0));
  let maxDist = 0;

  queue.push([y, x]);
  visited[y][x] = 1;

  while (queue.length) {
    const cur = queue.shift();

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

      if (0 <= ny && ny < row && 0 <= nx && nx < col) {
        if (!visited[ny][nx] && arr[ny][nx] === "L") {
          visited[ny][nx] = visited[cur[0]][cur[1]] + 1;
          maxDist = Math.max(maxDist, visited[ny][nx]);
          queue.push([ny, nx]);
        }
      }
    }
  }
  return maxDist - 1;
}

let ans = 0;

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (arr[i][j] === "L") {
      ans = Math.max(ans, bfs(i, j));
    }
  }
}

console.log(ans);

✔ 알고리즘 : BFS

✔ arr을 2중 for문으로 돌면서 육지인 경우 bfs탐색

✔ visted 배열을 통해 현재 정점이 방문한 점인지 체크

✔ bfs 탐색 시 이동할때마다 visted[ny][nx] 를 1씩 증가

✔ bfs를 시작하는 정점의 visited 값을 1로 설정하였으므로 bfs 탐색이 끝나고 return 할때 -1을 해준다

👉 vistied 초기값을 0이 아닌 1로 설정한 이유는 현재 정점을 방문했는지와 거리계산을 2개의 2차원배열이 아닌 1개의 2차원배열로 하기 위해서

✔ 난이도 : 백준 기준 골드 5