백준 2589 : 보물섬 - javascript(bfs)

문제 출처 

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

 

정답 풀이 

최단 거리 ? bfs 알고리즘을 사용하면 된다. 

 

시작점이 어디냐에 따라 최단 거리가 달라지니까, 

for 이중 반복문을 통해 모든 L을 시작점으로 둔다. 

 

그리고 bfs로 최대로 먼 곳을 갱신해준다. 

정답 코드

//상하좌우, 육지로 이동 
//한 칸 이동 - 한 시간 걸림 
//보물 : 최단 거리 이동하는데 , 가장 긴 시간이 걸리는 육지 두곳에 묻혀있음. 

//bfs 알고리즘 사용 
//어디서 시작하냐도 중요해서 전체 L 들어가야함 
//bfs로 탐색 후 그때의 max 값 구하기 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,m] = input.shift().split(' ').map(v => +v); 
let graph = input.map(row => row.split(''))

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

let max = 0

for(let i=0; i<n; i++){
    for(let j=0; j<m; j++){
        if(graph[i][j] === 'L'){
            bfs(i,j)
        }
    }
}

function bfs(x,y){
    const visited = Array.from({length: n}, () => new Array(m).fill(false)); 
    visited[x][y] = true; 
    const queue = [[x,y,0]]
    
    while(queue.length){
        let [cx, cy, time] = queue.shift()
        max = Math.max(max, time)
        for(let d = 0; d<4; d++){
            let nx = cx + dx[d]; 
            let ny = cy + dy[d]; 
            if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny]) continue;
            if(graph[nx][ny] === 'W') continue; 
            visited[nx][ny] = true; 
            queue.push([nx, ny, time+1])
        }
    }
}

console.log(max)