🖋️ 무인도 여행

# 문제 설명

지도에는 바다와 무인도들에 대한 정보가 표시
지도를 보고 각 섬에서 얼마나 머무를 수 있는지 알아보기

• 조건
  

  • 지도는 1 x 1 크기의 사각형들로 이루어진 직사각형 격자 형태
  • 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수 표시
    
    
  • X : 바다
  • 숫자 : 무인도 땅에 있는 식량
    
    
  • 연결된 땅들은 하나의 무인도
  • 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은
    해당 무인도에서 머물 수 있는 기간

• 매개 변수
  

  • 지도를 나타내는 문자열 배열 maps

• 반환값
  

  • 각 섬에서 최대 며칠씩 머무를 수 있는지
    배열에 오름차순으로 담아 return
  • 무인도가 없다면 -1 을 배열에 담아 return

• 📢 제한사항

  • 3 ≤ maps의 길이 ≤ 100
    • 3 ≤ maps[i]의 길이 ≤ 100
    • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열
    • 지도는 직사각형 형태

• 📰 입출력 예시

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

• CODE

function solution(maps) {
    const answer = [];
    
    const n = maps[0].length;
    const m = maps.length;  
    
    const getIsland = (start, maps) => {

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

        const q = [start];
        let sum = +maps[start[0]][start[1]];
        
        maps[start[0]][start[1]] = "X";
        while (q.length) {
            const [x, y] = q.pop();
            
            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];
                
                if (nx >= 0 && nx < m && ny >= 0 
                    && ny < n && maps[nx][ny] !== "X") {
                    q.push([nx, ny]);
                    sum += +maps[nx][ny];
                    maps[nx][ny] = "X";
                }
            }
        }
        return sum;
    }
    
    const board = maps.map((v) => [...v]);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] !== "X"){
                const island = getIsland([i, j], board);
                answer.push(island);
            }
        }
    }
    
    return answer.length ? answer.sort((a, b) => a - b) : [-1];
}

풀이

• BFS 완전 탐색을 통해 solution 구하기
  
  
• maps 를 이차배열 board 로 선언
• board 에서 X 가 아닌 idx 를 start 로 너비우선탐색
• 한 번 visit 한 격자는 "X" 로 변환
• answer 에 아무것도 없으면 [-1] 반환, 있으면 오름차순 정렬 후 반환