프로그래머스 - Level 2. 무인도 여행 / JavaScript (js)

문제설명

문제분석

이 문제는 입력 maps의 모든 요소를 순회하면서 상하좌우의 숫자로 이어진 구간의 합을 배열에 담아 리턴하는 문제입니다. bfs, dfs 모두 사용할 수 있지만 dfs를 사용할 경우 스택오버플로우가 날 수 있기때문에 bfs로 접근하도록 하겠습니다.

이해하기 쉽게 코드작성하기

function solution(maps) {
    const answer = [];
    const isVisited = new Array(maps.length).fill(0).map((x) => new Array(maps[0].length).fill(false));
    const isNotVisitedIsland = (r, c) => isVisited[r][c] === false && maps[r][c] !== 'X'
    
    const getSizeOfIsland = (r, c) => {
        if(isVisited[r][c] === true || maps[r][c] === 'X') return -1;
        let sum = 0;
        const q = [[r, c]];
        
        do{
            const [row, col] = q.shift();
            if(isNotVisitedIsland(row, col)) {
                isVisited[row][col] = true;
                sum += Number(maps[row][col]);
            }
            
            if(row - 1 >= 0 && isNotVisitedIsland(row - 1, col)) q.push([row - 1, col]);
            if(row + 1 < maps.length && isNotVisitedIsland(row + 1, col)) q.push([row + 1, col]);
            if(col - 1 >= 0 && isNotVisitedIsland(row, col - 1)) q.push([row, col - 1]);
            if(col + 1 < maps[0].length && isNotVisitedIsland(row, col + 1)) q.push([row, col + 1]);
        } while(q.length > 0)
        
        return sum;
    }
    
    for(let r = 0; r < maps.length; r++) {
        for(let c = 0; c < maps[0].length; c++) {
            if(isVisited[r][c] === false) {
                const sizeOfIsland = getSizeOfIsland(r, c);
                if(sizeOfIsland > -1) answer.push(sizeOfIsland);
            }
        }
    }
    
    return answer.length === 0 ? [-1] : answer.sort((a, b) => a - b);
}

방문했는지 확인하기 위해 isVisited 이중배열을 maps의 크기만큼 선언합니다. 그리고 각 요소를 접근하며 방문하지 않은 요소인 경우 상하좌우를 확인해 값을 더해주는 로직을 가진 getSizeOfIsland 함수를 선언했습니다. 마지막으로 maps를 순회하며 함수를 실행한 결과를 answer에 쌓아 조건에 맞게 리턴합니다.

그러나 그 결과는 시간 초과가 발생했습니다. 무엇이 문제일까요? 삽질을 하면서 코드도 깔끔하게 리팩토링 했습니다.

function solution(maps) {
    const answer = [];
    const map = maps.map(x => x.split(""));
    const isPossibleIsland = (r, c) => (r >= 0 && r < map.length && c >= 0 && c < map[0].length && map[r][c] !== 'X');
    
    for(let r = 0; r < map.length; r++) {
        for(let c = 0; c < map[0].length; c++) {
            if(map[r][c] === 'X') continue;
            let sum = 0;
            const q = [[r, c]];

            do{
                const [row, col] = q.shift();
                if(map[row][col] !== 'X') {
                    sum += Number(map[row][col]);
                    map[row][col] = 'X';
                }
                if(isPossibleIsland(row - 1, col)) q.push([row - 1, col]);
                if(isPossibleIsland(row + 1, col)) q.push([row + 1, col]);
                if(isPossibleIsland(row, col - 1)) q.push([row, col - 1]);
                if(isPossibleIsland(row, col + 1)) q.push([row, col + 1]);
            } while(q.length > 0)
            
            if(sum > 0) answer.push(sum);
        }
    }
    
    return answer.length === 0 ? [-1] : answer.sort((a, b) => a - b);
}

함수로 분리한 부분을 삭제하고, isVisited 배열을 대신해 maps의 배열형태를 사용키로 했습니다. 방문을 한 곳은 바다를 나타내는 'X'로 확인하면 isVisited의 t/f와 동일하게 사용할 수 있습니다. 예전에 실무에서 굳이 불리언 값을 설정하지 말고, 값만 담아두면 불리언 체크를 할 수 있다고 했던 선배 개발자의 조언을 담아보았습니다.

 

그러나 여전히 시간 초과가 발생합니다. 한참을 고민하다가 queue를 대신해 stack을 넣어봅니다.

 

function solution(maps) {
    const answer = [];
    const map = maps.map(x => x.split(""));
    const isPossibleIsland = (r, c) => (r >= 0 && r < map.length && c >= 0 && c < map[0].length && map[r][c] !== 'X');
    
    for(let r = 0; r < map.length; r++) {
        for(let c = 0; c < map[0].length; c++) {
            if(map[r][c] === 'X') continue;
            let sum = 0;
            const s = [[r, c]];

            do{
                const [row, col] = s.pop(); // shift -> pop
                if(map[row][col] !== 'X') {
                    sum += Number(map[row][col]);
                    map[row][col] = 'X';
                }
                if(isPossibleIsland(row - 1, col)) s.push([row - 1, col]);
                if(isPossibleIsland(row + 1, col)) s.push([row + 1, col]);
                if(isPossibleIsland(row, col - 1)) s.push([row, col - 1]);
                if(isPossibleIsland(row, col + 1)) s.push([row, col + 1]);
            } while(s.length > 0)
            
            if(sum > 0) answer.push(sum);
        }
    }
    
    return answer.length === 0 ? [-1] : answer.sort((a, b) => a - b);
}

모두 통과합니다. 큐랑 스택을 각각 이용하는 상황에서 1번 예제의 큰 섬을 기준으로 디버깅을 해보면, 처리되는 순서가 다음과 같습니다.

 

큐: [0, 1], [0,2], [1,1], [0, 3], [2,1], [1,3], [2, 2], [2, 3]

숫자: 5, 9, 1, 1, 2, 5, 3, 1

 

스택: [0, 1], [0, 2], [0, 3], [1, 3], [2, 3], [2, 2], [2, 1], [1, 1]

숫자: 5, 9, 1, 5, 1, 3, 2, 1

 

지금까지 알아낸 정보는 여기까지입니다. row 접근이 col 접근보다 빠른가? 싶은 생각이 잠깐 들었지만, 어차피 배열에서 하나씩 꺼내 확인하는 건 똑같은데... 싶기도 하고 그렇습니다.