프로그래머스 [Lv. 2] 무인도 여행 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(maps) {
    const answer = [];
    
    const n = maps.length;
    const m = maps[0].length;
    
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const isValid = (nr, nc) => {
        return 0 <= nr && nr < n && 0 <= nc && nc < m;
    };
    
    let visited = Array(n).fill().map(() => Array(m).fill().map(() => 0));    

    const bfs = (sr, sc) => {
        q = [[sr, sc]];
        let cnt = parseInt(maps[sr][sc]);
        visited[sr][sc] = 1;
        while (q.length) {
            const [r, c] = q.shift();
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (isValid(nr, nc) && maps[nr][nc] !== "X" && visited[nr][nc] == 0) {
                    visited[nr][nc] = 1;
                    q.push([nr, nc]);
                    cnt += parseInt(maps[nr][nc]);
                };
            };
        };
        return cnt;
    };
    
    
    for (let sr = 0; sr < n; sr++) {
        for (let sc = 0; sc < m; sc++) {
            if (visited[sr][sc] == 1 || maps[sr][sc] === "X") {
                continue;
            };
            const tmp = bfs(sr, sc);
            answer.push(tmp);
        };
    };
    
    answer.sort((a, b) => a - b);
    const result = answer.length ? answer : [-1];
    return result;
}

풀이 방법

1. 방문 배열을 만든다.
2. X가 아닌 sr, sc를 찾고 방문 배열이 0이면 그래프를 순회한다.
3. 순회하면서 cnt에 해당 위치의 값을 더해준다.
4. cnt를 anwer에 넣고 정렬한다.
5. 정렬 이후에 answer값이 비어있으면 -1을 반환한다.
6. answer값이 있으면 위에 정렬한 answer가 결과 값이 된다.

느낀점

• 쉽지만 단순한 실수를 했다.
• visited[sr][sc] or maps[sr][sc] == "X" 인데 and 연산으로 묶어서 시간이 조금 지체되었다.