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

❓문제설명

무인도 여행

프로그래머스

---

🔍문제해석

어떤걸 풀어야 할까?

바다에 떠있는 섬들의 각 식량합을 구하자.

이차원배열에 "X"값이 있는 칸은 바다고 그 외의 칸들은 섬이다.

섬의 칸에는 숫자가 있고 그 숫자를 모두 더하면 그게 하나의 섬의 식량합이다.

만약 방문할 수 있는 섬이 없다면 배열에 -1을 담아서 리턴

---

🧐문제풀이

• 문제 풀이 구상

섬의 식량값을 다 더하려면 아무래도 이중for문을 사용해야 하긴하다.

하지만 모든 배열을 다 방문한다면 무조건 시간초과가 될 것이다.

그 점을 방지하기 위해 한번 방문한 섬은 모두 "X"를 대입해서 바다로 처리한다.

그렇게 되면 한번 방문했던 섬은 합산이 끝나면 바다가 되어버리고, 그 다음에 최초로 방문한 숫자칸은 섬의 시작이 될 것이다.

그 시작점부터 출발하여 해당 섬의 식량합을 계산한다.

• 알고리즘 선택

첫 방문한 섬의 시작점부터 상하좌우를 계산해서 섬 안인지 체크를 하고 식량을 더해야하기 때문에

bfs 방식으로 진행하였다.

 

---

！제출코드

1. 한번 방문하면 "X"로 대입하기 위해, String[]을 이차원 배열로 변경
2. 이중for문을 돌면서 "X"가 아닌 칸은 섬으로 간주, 그때부터 섬을 탐색하기 위해 BFS를 시작한다.
3. 섬의 초기 식량값은 첫 시작칸.
4. 이동가능 한 칸(== 섬)을 queue에 넣어서 다 빌때까지 탐색한다.
5. 상하좌우로 계산하여 다음칸으로 이동가능한지 확인하고, 가능하다면 식량을 더하고 바다로 처리한다.
6. ArrayList에 각 섬의 식량합을 추가한다. 만약 ArrayList가 텅비었다면 -1을 갖고 있는 배열을 리턴한다.

 

import java.util.*;
class Solution {
    static String [][] map;
       public static int[] solution(String[] maps) {

       // (1)
        map = new String[maps.length][maps[0].length()];
        
        for(int i = 0; i < maps.length; i++) {
            for(int j = 0; j < maps[i].length(); j++) {
                map[i][j] = maps[i].charAt(j) + "";
            }
        }

        List<Integer> answerList = new ArrayList<>();
        
        // (2)
        for(int i = 0; i < map.length; i++) {
        
            for(int j = 0; j < map[i].length; j++) {
            
                if(!"X".equals(map[i][j])) {
                
                   int meal = Integer.parseInt(map[i][j]);
                   map[i][j] = "X";
                   int mealSum =  bfs(new int[]{i,j}, meal);
                   answerList.add(mealSum);

                }
            }
        }

        // (6)
        Collections.sort(answerList);
        int[] answer;
        if(!answerList.isEmpty()) answer = answerList.stream().mapToInt(i -> i).toArray();
        else answer = new int[]{-1};
        return answer;
    }
    
    static int  bfs(int[] start ,int meal){

        int[]dy = {0,0,1,-1};
        int[]dx = {1,-1,0,0};
        // (3)
        int mealSum = meal;
        
        // (4)
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0],start[1]});
        
        while(!queue.isEmpty()){
        
            int size = queue.size();
            
            for(int i = 0; i < size; i++) {
            
                int[] current = queue.poll();
                
                for(int j = 0; j < dy.length; j++) {
                
                    int newY = current[0] + dy[j];
                    int newX = current[1] + dx[j];
                    
                    if(newY > -1 && newY < map.length && newX > -1 && newX < map[0].length && !map[newY][newX].equals("X")) {
                        // (5)
                        mealSum +=Integer.parseInt(map[newY][newX]);
                        map[newY][newX] = "X";
                        queue.offer(new int[]{newY,newX});
                    }
                }
            }
        }
       return mealSum;
    }
}