백준 2589번: 보물섬(javscript, BFS, 완전탐색)

전형적인 BFS이며 브루탈 포스(완전탐색) 문제이다. 

 

문제에서 보물이 묻혀있는 곳 두 거리간의 최단거리를 요구하고 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 

 

최단거리로 이동할 수 있는 방법은 BFS 알고리즘이다. 왜 BFS알고리즘이 최단거리인지는 트리를 어떻게 탐색하는 지를 생각해보면 쉽게 이해할 수 있다.

 

따라서 이 문제는 완전탐색을 통해 BFS로 육지마다 다른 육지들로 이동할 때의 거리들 중 최대거리를 구하면 그 값이 답이 된다. 또한 BFS는 DFS와 다르게 한번의 이동에 주변을 다 탐색하므로 이동할 때마다 이동거리를 증가시키면 안되고 이전 이동거리에 1을 더해서 이동거리를 계산해야 한다.

 

위 생각을 토대로 짠 코드는 다음과 같다.

 

주의할 점으로는 BFS의 구현에 있어서다.

 

visited배열을 사용할 때 방문여부를 체크하는 코드를 queue에 다음 원소를 넣을때 체크해야 시간이 크게 소요되지 않는다.  

const fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [ROW, COLUMN] = input[0].split(' ').map(a => Number(a))


// BFS 함수 정의
const dx = [0, 0, 1, -1]
const dy = [1, -1, 0, 0]
function bfs(r, c){
    let max2 = 0
    let queue = [[r,c,0]]
    visited[r][c]= true
    while(queue.length){
        const cash =  queue.shift()
        if(cash[2] >= max2){
            max2 = cash[2]
        }
        for (let i=0; i<4; i++){
            const nrow = cash[0] + dx[i]
            const ncol = cash[1] + dy[i]
            if(0 <= nrow && nrow < ROW && 0 <= ncol && ncol < COLUMN && board[nrow][ncol] === 'L' && !visited[nrow][ncol]) {
                // BFS이므로 한번 이동할때마다 이동거리가 1증가하는것이 아닌 이전 이동거리에서 +1 해야함
                queue.push([nrow, ncol, cash[2]+1])
                // visited 체크를 여기서 해야함
                visited[nrow][ncol] = true
            }
        }
    }
    return max2
}

const board = Array.from({ length: ROW}, () => []);
for(let i=0; i<ROW; i++){
    board[i] = input[i+1].split('')
}

let answer = Number.NEGATIVE_INFINITY

for (let row = 0; row < ROW; row++) {
    let min = 0
    for (let col = 0; col < COLUMN; col++) {
        if (board[row][col] === 'L') {
            visited = Array.from({length: ROW}, () => [])
            for (let _ = 0; _ < ROW; _++) {
                visited[_] = Array.from({length: COLUMN}, () => []).fill(false)
            }
            min = bfs(row, col)
            if (min >= answer) {
                answer = min
            }
        }
    }

}

console.log(answer)