[백준 2589] 보물섬 - bfs,너비탐색 알고리즘, javascript,nodejs

문제 :

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

2589번: 보물섬

 

알고리즘 :

1. 이 문제는 전형적인 bfs 문제이지만 시작 지점을 모두 검사해보아야 한다.

2. 따라서 2중 for문을 돌면서 거리 탐색을 한다.

 

문제풀이 : 

1. 입력값에서 row와 col, map,dist를 설정한다.

const [row , col] = input[0].split(' ').map(Number)
const map = input.slice(1).map(v=>v.split('').filter(a=>a!=='\r'))
let dist = 0;

 

2. 2중 for문을 돌면서 bfs 탐색과정을 실행한다.

이때, disf(거리)를 Math.max로 반복해서 초기화를 한다. (또는 배열로 저장해서 마지막에 max값을 리턴해도 된다.)

for (let i=0;i<row;i++){
  for(let j=0;j<col;j++){
    let visit = map.map(v=>v.map(a=>0))
    if(!visit[i][j]&&map[i][j]==="L") {
      // visit[i][j]=1;
      let queue = [[i,j]]
      while (queue.length){
        const [y,x] = queue.shift()
        const dy = [-1,1,0,0]
        const dx = [0,0,-1,1]
      
        for(let k=0;k<4;k++){
          const ny = y+dy[k]
          const nx = x+dx[k]
          if(ny>=0&&nx>=0&&ny<row&&nx<col&&map[ny][nx]==="L"
          &&!visit[ny][nx]){
            visit[ny][nx] = visit[y][x] + 1
            // console.log("y : "+y+"x : "+x)
            // console.log(visit)
            dist = Math.max(dist,visit[ny][nx])
            queue.push([ny,nx])
          }
        }
        visit[i][j] = -5
      }
    }
  }
}

3. 전체 코드

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

const [row , col] = input[0].split(' ').map(Number)
const map = input.slice(1).map(v=>v.split('').filter(a=>a!=='\r'))
let dist = 0;
// console.log(map)


// console.log(visit)
for (let i=0;i<row;i++){
  for(let j=0;j<col;j++){
    let visit = map.map(v=>v.map(a=>0))
    if(!visit[i][j]&&map[i][j]==="L") {
      // visit[i][j]=1;
      let queue = [[i,j]]
      while (queue.length){
        const [y,x] = queue.shift()
        const dy = [-1,1,0,0]
        const dx = [0,0,-1,1]
      
        for(let k=0;k<4;k++){
          const ny = y+dy[k]
          const nx = x+dx[k]
          if(ny>=0&&nx>=0&&ny<row&&nx<col&&map[ny][nx]==="L"
          &&!visit[ny][nx]){
            visit[ny][nx] = visit[y][x] + 1
            // console.log("y : "+y+"x : "+x)
            // console.log(visit)
            dist = Math.max(dist,visit[ny][nx])
            queue.push([ny,nx])
          }
        }
        visit[i][j] = -5
      }
    }
  }
}
// console.log(visit)
console.log(dist)