[99클럽 코테 스터디 32일차 TIL] 프로그래머스 - 무인도 여행

99클럽 코테 스터디 32일차 TIL 입니다.

[level 2] 무인도 여행 - 154540

문제 링크

문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

---

제한사항

• 3 ≤ maps의 길이 ≤ 100

  • 3 ≤ maps[i]의 길이 ≤ 100

  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.

  • 지도는 직사각형 형태입니다.

---

입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

---

입출력 예 설명

입출력 예 #1

위 문자열은 다음과 같은 지도를 나타냅니다.

image1

연결된 땅들의 값을 합치면 다음과 같으며

image2

이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.

입출력 예 #2

위 문자열은 다음과 같은 지도를 나타냅니다.

image3

섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.

---

풀이 코드

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        int row = maps.length;
        int col = maps[0].length();
        int[][] pos = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] ms = new int[row][col];
        for (int i = 0; i < row; i++) {
            char[] m = maps[i].toCharArray();
            for (int j = 0; j < col; j++) {
                ms[i][j] = m[j] == 'X' ? 0 : m[j] - '0';
            }
        }
        boolean[][] visited = new boolean[row][col];
        
        List<Integer> foods = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visited[i][j] || ms[i][j] == 0) continue;
                Deque<Integer[]> dq = new ArrayDeque<>();
                dq.add(new Integer[]{i, j});
                int cnt = 0;
                while (!dq.isEmpty()) {
                    Integer[] l = dq.pop();
                    int lr = l[0];
                    int lc = l[1];
                    visited[lr][lc] = true;
                    cnt += ms[lr][lc];
                    for (int[] p : pos) { // 상하좌우 순회
                        int r = p[0] + lr;
                        int c = p[1] + lc;
                        if (r >= 0 && r < row &&
                            c >= 0 && c < col &&
                            !visited[r][c]) {
                            visited[r][c] = true;
                            if (ms[r][c] == 0) continue;
                            dq.add(new Integer[]{r, c});
                        }
                    }
                }
                if (cnt != 0) foods.add(cnt);
            }
        }
        if (foods.isEmpty()) return new int[]{-1};
        Collections.sort(foods);
        int[] answer = new int[foods.size()];
        for (int i = 0; i < foods.size(); i++) answer[i] = foods.get(i);
        return answer;
    }
}

• Time : 9.07 ms

• Memory : 77.7 MB

BFS 로 풀었는데 반례 하나를 생각 못해서 정말 오래 헤맸다. 처음 풀이에는 if (visited[i][j] || ms[i][j] == 0) continue; 조건문에서 ms[i][j] == 0 을 뺐었는데 아래와 같은 경우에 틀리게 됐었다.

• input - ["X1X", "1XX"]

• expected - [1, 1]

• output - [2]

ms 배열 값이 0 인 경우는 음식이 없는 경우인데 위 예시일 때 맨 처음 좌표(0, 0)에서 큐에 (1, 0) 과 (0, 1) 을 추가하게 되고 이로 인해 cnt 값에 각 좌표의 값인 1이 추가되면서 결과 값 2 가 반환된다. 따라서 방문한 좌표뿐만 아니라 좌표 값이 0 인 경우에도 건너 뛰도록 해야 한다.

---

돌아보기

조금만 차근 차근 확인했으면 반례를 조금 더 빠르게 알아챌 수 있었을 것 같다.

---

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL