무인도 여행, JavaScript

cptkuk91·2023년 4월 10일
1

Algorithm

목록 보기
159/161

문제

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

코드

function solution(maps) {
    let result = [];

    maps = maps.map(row => row.split('').map(cell => (cell === 'X' ? 'X' : parseInt(cell, 10))));

    function dfs(row, col) {
        if (row < 0 || col < 0 || row >= maps.length || col >= maps[row].length || maps[row][col] === 'X') {
            return 0;
        }

        let islandSum = maps[row][col];
        maps[row][col] = 'X';

        islandSum += dfs(row - 1, col);
        islandSum += dfs(row + 1, col);
        islandSum += dfs(row, col - 1);
        islandSum += dfs(row, col + 1);

        return islandSum;
    }

    for (let row = 0; row < maps.length; row++) {
        for (let col = 0; col < maps[row].length; col++) {
            if (maps[row][col] !== 'X') {
                const islandSum = dfs(row, col);
                result.push(islandSum);
            }
        }
    }
    
    result.sort((a, b) => a - b);

    return result.length === 0 ? [-1] : result;
}

풀이

우선 첫줄, 마지막줄, 첫줄시작, 첫줄 마지막, 끝줄 시작, 끝줄 마지막을 주의해야한다.
반복문을 통해서 maps[row][col] !== "X" 경우 dfs통해 상하좌우 숫자를 더해준다.

for (let row = 0; row < maps.length; row++) {
    for (let col = 0; col < maps[row].length; col++) {
        if (maps[row][col] !== 'X') {
            const islandSum = dfs(row, col);
            result.push(islandSum);
        }
    }
}

상하좌우(부르기 쉽게 표시) 숫자로 연결 된 경우 숫자를 더한다.

islandSum += dfs(row - 1, col);
islandSum += dfs(row + 1, col);
islandSum += dfs(row, col - 1);
islandSum += dfs(row, col + 1);

만약 "X"밖에 없는 경우 기존 선언된 result = [] 배열을 반환하기 때문에, "X"밖에 없는 경우
result를 구한 후 문제 요구사항에 맞춰 sort() 한번 했습니다.

result.length === 0 ? [-1] : result

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)

0개의 댓글