프로그래머스[Level2] 무인도 여행 - JavaScript

문제 설명

문제 링크

프로그래머스[Level2] 무인도 여행

접근 방법

1. 연결되어 있는 섬 찾아서 더해주기
2. dfs,bfs 문제
3. (현재 x좌표,현재 y좌표)를 기준으로 상하좌우 탐색 해서 연결이 되어 있는지 연결이 되어있다면 Sum에 +해주기

코드

function solution(maps) {
    var answer = [];
    let map = initMap(maps);
    // 연결되어 있는 공간이 없으면 -1 리턴
    if(map ==-1) return [-1];
    let visited = initVisited(maps);

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

    for(let col=0;col<maps.length;++col){
        for(let row =0;row<maps[col].length;++row){
            if(!visited[col][row]){
                let result = bfs(row,col,visited,map,dx,dy,map[col][row]);
                if(result>0) answer.push(result);
            }
        }
    }
    return answer.sort((a,b)=> a-b);
}

// bfs 구현
function bfs(x,y,visited,map,dx,dy,sum){
    let queue = [];
    queue.push([x,y]);
    visited[y][x]= true;
    while(queue.length!=0){
        let q = queue.shift();
        let x = q[0];
        let y = q[1];

        for(let dir = 0;dir<4;++dir){
            let nx = x+dx[dir];
            let ny = y+dy[dir];

            if(nx>=0&&nx<map[0].length&&ny>=0&&ny<map.length&&map[y][x]!=-1){
                if(!visited[ny][nx]&&map[ny][nx]!=-1){
                    sum+=map[ny][nx];
                    visited[ny][nx]=true;
                    queue.push([nx,ny]);
                }
            }
        }
    }
    return sum;   
}

// map을 X라면 -1로 바꿔주었습니다. 작성하는 사람마다 다르지만 저는 int형식으로 하고 싶어서 init함수 만들어 줬습니다.
function initMap(maps){
    let map = [];
    let isTrue = false;
    for(let col=0;col<maps.length;++col){
        let m = [];
        for(let row = 0; row<maps[col].length;++row){
            if(maps[col][row]==='X') m[row]=-1;
            else {
                m[row] = parseInt(maps[col][row]);
                isTrue = true;
            }
        }
        map.push(m);
    }
    if(!isTrue) return -1;
    else return map;
}
// visited 방문했는지 여부를 초기화 해주었습니다.
function initVisited(maps){
    let visited = [];
    for(let col=0;col<maps.length;++col){
        let visit = [];
        for(let row= 0;row<maps[col].length;++row){
            visit[row]=false;
        }
        visited.push(visit);
    }
    return visited;
}