[프로그래머스] Level2 - 무인도 여행(Javascript)

프로그래머스

▶ 문제 요약

1. 지도에 바다와 무인도들에 대한 정보가 표시돼 있다.

2. 지도의 X는 바다를 나타내고 숫자는 무인도를 나타낸다. 이때 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룬다.

3. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다. 

4. 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return하는 함수 작성

 

▶ 정답 코드

function solution(maps) {
    let answer = [];
    // 붙어있는 문자열을 떼주기
    let newMaps = maps.map(el => el.split(""));
    // 방문 배열을 만들기 위해 배열 사이즈 재기 
    let n = newMaps[0].length, m = newMaps.length; 
    let visited = Array.from(Array(m), () => Array(n).fill(false));
    
    // 사방탐색에 필요한 정보
    const dx = [-1, 0, 0, 1], dy = [0, -1, 1, 0];
    
    function bfs(x, y) {
        let queue = [[x, y]];
        // 시작지점 방문표시
        visited[x][y] = true;
        
        // 시작지점의 식량을 담는다. 
        let days = Number(newMaps[x][y]);
        
        // queue에 원소가 있을때까지 돌기
        while (queue.length > 0) {
            // 탐색을 위해 queue에 있는 x,y 추출
            let [x, y] = queue.shift();
            
            // 사방탐색 진행
            for (let i = 0; i < 4; i++) {
                let nx = dx[i] + x
                let ny = dy[i] + y
                
                // 범위가 벗어나지 않은지 체크(행과, 열)
                if (-1 < nx && nx < m && -1 < ny && ny < n) {
                    // 방문한적 없거나 숫자인 경우
                    if (newMaps[nx][ny] !== "X" && !visited[nx][ny]) {
                        // 방문표시
                        visited[nx][ny] = true;
                        // 숫자형으로 변환하고 누적시키기
                        days += Number(newMaps[nx][ny]);
                        // queue에 다음 순회할 곳 넣어주기
                        queue.push([nx, ny]);
                    }
                }
            }
        }
        return days;
        
    }
    // 돌지 않은 부분들을 돌기 시작한다.
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // 방문하지 않은 곳이나 숫자인경우 돌기 시작한다.
            if (!visited[i][j] && newMaps[i][j] !== "X") {
                let result = bfs(i, j);
                answer.push(result);
            }
        }
    }
    
    // 길이가 0이면 지낼 수 있는 무인도가 없으므로 1을 넣어주고
    // 아니면 정렬해준다. 
    answer.length === 0 ? answer.push(-1) : answer.sort((a, b) => a - b);
    return answer;
}

 

▶ 풀이 과정

1. 입력값은 현재 배열안에 문자열 형태로 되어있다. 그러나 우리가 탐색을 하기 위해서는 분리시켜야 한다. 그래서 split() 메서드를 사용해서 분리시킨다. 

 

2. 방문 배열을 만들기 위해서 행과 열의 크기를 변수에 담았고, 그것을 바탕으로 방문표시할 배열을 행과 열의 크기만큼 Array.from() 활용해서 만들었다. 초깃값은 false로 했다.

 

3. 사방탐색에 필요한 방향정보를 담아준다. 

 

4. bfs 함수를 만들어서 처음에 시작지점을 넣어준다. 그리고 시작지점은 방문표시를 해주다. 문제에서 핵심인 며칠 머무를 수 있는지 계산하기 위해서 시작지점의 식량을 담아준다. 

 

5. queue가 존재할 때까지 돌면서 다음 방향을 탐색하기 위해서 shift() 메서드를 활용해서 queue에서 빼준다. 사방탐색을 진행한다. 

 

6. 다음 방향이 배열의 범위가 벗어나지 않는지 체크해야 한다. nx는 행의 크기 ny는 열의 크기를 비교해야한다. 그리고 방문한 적이 없거나 방문한 곳이 식량이 있는 곳이라면 방문표시를 위해서 false를 true로 바꿔주고 숫자를 계속 누적시킨다. 그리고 다음 방향 탐색을 위해서 현재의 방향을 큐에 넣어준다. 

 

7. 6번까지만 하면 한 번만 탐색하고 종료되니 우리가 원하는 것은 모든 지도를 탐색하는 것이니 이중 for문을 활용해서 위와 비슷한 방식으로 방문하지 않았거나 숫자인 경우에는 탐색을 해준다. 그리고 결과값을 배열에 담아준다. 

 

8. 배열의 길이가 0이면 지낼 수 있는 무인도가 없으므로 -1을 넣어주고 아니면 오름차순 정렬을 해준다.