[JS] 2Level / 연습문제 / 무인도 여행

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

문제 풀이 방법

이 문제는 BFS 알고리즘을 이용해서 풀었다.

BFS로 풀이한 까닭은 혹시 모르는 시간 초과 에러를 방지하기 위함이다.

DFS로 풀이하게 되면 갈래길에서 다시한번 노드를 역행하는 방식이 걱정되어서 이다.

 

방문했던 노드를 기록하기 위해 0으로 채워진 2차원 배열과

 

bfs 함수 내부에 검증할 섬의 숫자를 담는 큐, 머물 수 있는 일 수를 선언해 큐 내부가 비어질때 까지 진행.

 

처음 시작하는 점을 기준으로 상하좌우 모두 유효한지 검증 후 현재 위치한 부분의 방문 여부를 기록, 큐에 다음 검증할 부분을 추가, 묵을 수 있는 일수에 현재 부분의 일수를 더해준다.

 

코드

const solution = (maps) => {
    let answer = [];
    let [yL, xL] = [maps.length, maps[0].length];
    let visited = Array.from({ length: yL }, () => Array(xL).fill(0));
    
    const bfs = (y, x) => {
        let direction = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        let que = [[y, x]];
        let cnt = 0;
        cnt += Number(maps[y][x]);
        visited[y][x] = true;
        
        while(que.length){
            let [py, px] = que.shift();
            for(let i=0; i<4; i++){
                let ny = py + direction[i][0];
                let nx = px + direction[i][1];
                
                if(ny >= 0 && ny < yL && nx >= 0 && nx < xL && !visited[ny][nx] && maps[ny][nx] !== 'X'){
                    cnt += Number(maps[ny][nx]);
                    que.push([ny, nx]);
                    visited[ny][nx] = true;
                }
            }
        }
        return cnt;
    }
    
    for(let i=0; i<yL; i++){
        for(let j=0; j<xL; j++){
            if(maps[i][j] !== 'X' && !visited[i][j]){
                answer.push(bfs(i, j));
            }
        }
    }
    
    if(!answer.length) return [-1];
    return answer.sort((a, b) => a - b);
}