프로그래머스 코딩테스트 연습 - 무인도 여행 JavaScript

이번 문제는 이차원 배열을 방문하면서, 연결된 유효한 값의 범위와 값을 구하는 문제이다.

기본적으로 dfs방식을 사용하였으며, 방문했는지 확인할 수 있는 값을 설정하여 문제를 해결하였다.

function solution(maps) {
    // X는 바다, 숫자는 무인도
    // 상하좌우로 연결된 무인도의 숫자의 합은 머물 수 있는 날짜 수
    const answer = [];
    const checkValid = (x, y) => maps.length - 1 >= x && x >= 0 && maps[x].length - 1 >= y && y >= 0;
    const mapDfs = (visited, x, y) => {
        // x, y 방문
        let sum = parseInt(maps[x][y]);
        visited[x][y] = true;
        // 상하좌우 이동
        if(checkValid(x - 1, y) && !visited[x - 1][y] && maps[x - 1][y] !== 'X') {
            sum += parseInt(mapDfs(visited, x - 1, y));
        }
        if(checkValid(x + 1, y) && !visited[x + 1][y] && maps[x + 1][y] !== 'X') {
            sum += parseInt(mapDfs(visited, x + 1, y));
        }
        if(checkValid(x, y - 1) && !visited[x][y - 1] && maps[x][y - 1] !== 'X') {
            sum += parseInt(mapDfs(visited, x, y - 1));
        }
        if(checkValid(x, y + 1) && !visited[x][ y + 1] && maps[x][y + 1] !== 'X') {
            sum += parseInt(mapDfs(visited, x, y + 1));
        }
        return sum;
    }
    
    // 방문 시작
    const visited = [];
    for(let i = 0; i < maps.length; i++) {
        visited.push(new Array(maps[i].length).fill(false));
    }
    for(let i = 0; i < maps.length; i++) {
        for(let j = 0; j < maps[i].length; j++) {
            if(!visited[i][j] && maps[i][j] !== 'X') {
                answer.push(mapDfs(visited, i, j));
            }
        }
    }
    if(answer.length === 0) {
        return [-1];
    }
    return answer.sort((a, b) => a - b);
}

모든 경우의 수를 파악할 수 있도록, 모든 요소에서 확인을 하였다.

 

다른 사람이 푼 방법을 살펴보았는데, bfs, stack, queue 등 다양한 방법을 사용할 수 있는 것 같았다.

bfs는 개인적으로 약한 부분이라고 생각했기에 이 부분에 대해서 다른 사람의 코드를 보고 배우고자 하였다.