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

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

문제

• 지도에는 바다와 무인도에 대한 정보가 담겨있다.
• 각각의 격자 칸에는 식량의 수가 담겨있고, 무인도의 모든 칸의 합은 해당 무인도에서 머물 수 있는 최대 날짜이다.
  • X는 바다를 나타낸다.
• 상,하,좌,우로 연결되는 땅들은 하나의 무인도를 이룬다.
• 지도를 나타내는 문자열 maps가 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return하시오.

제한사항

• 3 ≤ maps의 길이 ≤ 100
  • 3 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
  • 지도는 직사각형 형태입니다.

코드

import java.util.*;
class Solution {
    public int[] solution(String[] maps) {
        ArrayList<Integer> foods = new ArrayList<Integer>();
        char[][] charMap = new char[maps.length][];
        for (int i = 0; i < maps.length; i++) {
            charMap[i] = maps[i].replaceAll("X","0").toCharArray();
        }

        int row = maps.length;
        int col = maps[0].length();
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a,b)->a[0]-b[0]);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(charMap[i][j]=='0') {
                    continue;
                }
                int food = 0;
                pq.offer(new int[] {charMap[i][j],i,j});
                charMap[i][j] = '0';
                while(!pq.isEmpty()) {
                    int[] cur = pq.poll();
                    food += cur[0]-'0';

                    if(cur[1]-1 >= 0 && charMap[cur[1]-1][cur[2]] != '0') {//상
                        pq.offer(new int[] {charMap[cur[1]-1][cur[2]],cur[1]-1,cur[2]});
                        charMap[cur[1]-1][cur[2]] = '0';
                    }

                    if(cur[1]+1 < row && charMap[cur[1]+1][cur[2]] != '0') {//하
                        pq.offer(new int[] {charMap[cur[1]+1][cur[2]],cur[1]+1,cur[2]});
                        charMap[cur[1]+1][cur[2]] = '0';
                    }

                    if(cur[2]-1 >= 0 && charMap[cur[1]][cur[2]-1] != '0') { //좌
                        pq.offer(new int[] {charMap[cur[1]][cur[2]-1],cur[1],cur[2]-1});
                        charMap[cur[1]][cur[2]-1] = '0';
                    }

                    if(cur[2]+1 < col && charMap[cur[1]][cur[2]+1] != '0') { //우
                        pq.offer(new int[] {charMap[cur[1]][cur[2]+1],cur[1],cur[2]+1});
                        charMap[cur[1]][cur[2]+1] = '0';
                    }
                }
                foods.add(food);
            }
        }

        Collections.sort(foods);

        return foods.size() == 0 ? new int[]{-1} : foods.stream().mapToInt(i->i).toArray();
    }
}

풀이

• 제한사항을 보면 맵의 크기가 100*100으로 전형적인 완전탐색문제다.
• 주어지는 maps는 String형이지만 문제에서 다루어야 하는건 숫자이므로 간단하게 char형으로 변환한 뒤 사용하면 된다.
  • 바다의 경우 replaceAll함수로 전부 0으로 변환시킨다.
• 바다가 아닌 땅을 찾으면 bfs든dfs든 완전탐색으로 무인도의 크기를 탐색하면 된다.
• 정렬의 경우 Collection의 sort를 사용했는데, 이 경우 배열로 리턴해야 하기 때문에 int배열로 변환시켜주어야 한다. 따라서 stream을 이용해 변환시켜주면 된다.