230201 프로그래머스 무인도 여행(자바/자바스크립트)

매일 매일 하루 한 문제씩.
꾸준히 이어가는 코딩테스트 풀이 기록 ✅

오랜만에 프로그래머스 문제를 풀었다.
정답률이 꽤 낮은 level 2 문제였는데 우선 나는 못풀었고..;
DFS 숙련이 부족하다는 생각이 들었고, 어제 풀었던 queen's attack과 비슷하다는 느낌이 들었는데 또다시 풀이가 안되는... 우선 내일 면접이 끝난 후에 동료분이 추천해준 코딩테스트 강의를 결제하련다.

오늘 문제 풀이는 모두 다른 분들의 플이이기 때문에 각 풀이마다 출처를 남길 예정.

---

문제 링크

프로그래머스 무인도 여행

---

Java

참고한 블로그 링크

풀이를 참고하려고 서치를 하다보니 maps의 범위가 100 x 100인 것을 보고 전형적인 완전탐색이라는 내용을 확인할 수 있었다.

완전탐색인지는 잘 모르겠는데 어쨌든 어제 풀었던 queens's attack과 왠지 비슷하다고 생각했고 아마 그런 것 같다.

계속 알고리즘에 발목을 잡히는 것 같은데... 코딩테스트가 취업의 능사는 아니겠지만 그래도 테스트를 통과하고 싶다는 열망이 아직은(?) 남아있기에ㅎㅎ..

이 문제를 다시 풀었을 땐 즐거운 마음으로 통과시킬 수 있기를 바라며 풀이를 기록한다.

import java.util.*;

class Solution {
    int[][] map;
    List<Integer> answer = new LinkedList<>();

    public int[] solution(String[] maps) {
        // maps 배열 int로 변환
        map = new int[maps.length][maps[0].length()];

        for (int i = 0; i < maps.length; i += 1) {
            char[] mapCharArray = maps[i].toCharArray();

            for (int j = 0; j < mapCharArray.length; j += 1) {
                char character = mapCharArray[j];

                if (character == 'X') {
                    map[i][j] = -1;
                    continue;
                }

                map[i][j] = character - '0';
            }
        }

        for (int i = 0; i < map.length; i += 1) {
            for (int j = 0; j < map[0].length; j += 1) {
                int isLandSum = dfs(i, j);
                if (isLandSum > 0) {
                    answer.add(isLandSum);
                }
            }
        }

        // 무인도가 없는 경우
        if (answer.size() == 0) {
            return new int[]{-1};
        }

        // 무인도가 있는 경우
        Collections.sort(answer);

        int[] answerArray = new int[answer.size()];

        for (int i = 0; i < answerArray.length; i += 1) {
            answerArray[i] = answer.get(i);
        }

        return answerArray;
    }

    // dfs 알고리즘
    public int dfs(int i, int j) {
        // 배열의 범위를 벗어나면 return
        if (i < 0 || j < 0 || i >= map.length || j >= map[0].length) {
            return 0;
        }

        // 이미 들린 곳
        if (map[i][j] == -1) {
            return 0;
        }

        int temp = map[i][j];
        map[i][j] = -1; // 들린 상태 저장

        return temp + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1);
    }
}

---

Javascript

자바스크립트 풀이는 다른 사람들의 풀이 가장 상단에 있는 내용(닉네임 Hoejun Jang)을 가져왔다.

과하지 않은 선에서 let, for문을 사용하는 점이 좋다고 생각했고 새롭게 알게된 것은 Array.from()이라는 함수인데 어떻게 사용하는 건지 잘 모르겠다. 자바스크립트 공부하면서 또다시 만날 것 같은데.. 흠.

어쨌든 keep.

function solution(maps) {
    const rowLen = maps.length;
    const colLen = maps[0].length;
    const answer = [];
    const SEA = 'X';
    const dr = [-1,0,1,0];
    const dc = [0,1,0,-1];
    const visited = Array.from(Array(rowLen),() => new Array(colLen).fill(false));
    const util = (row,col) => {
        let foodSum = parseInt(maps[row][col]);
        for(let dir=0;dir<4;dir++){
            const nr = row + dr[dir];
            const nc = col + dc[dir];
            if(nr >= 0 && nr < rowLen && nc >= 0 && nc < colLen && maps[nr][nc] !== SEA && !visited[nr][nc]){
                visited[nr][nc] = true;
                foodSum += util(nr,nc);
            }
        }
        return foodSum;
    }
    for(let row = 0;row<rowLen;row++){
        for(let col=0;col<colLen;col++){
            const curr = maps[row][col];
            if(curr !== SEA && !visited[row][col]){
                visited[row][col] = true;
                const food = util(row,col);
                answer.push(food);
            }
        }
    }
    if(answer.length === 0){
        return [-1];
    }
    answer.sort((a,b) => a-b);
    return answer;
}

---

다른 말 필요 없다. 분발하자.