[프로그래머스] 무인도 여행 -Java(자바)

 

문제 이해

• 무인도 여행을 하려고 한다. 각 섬마다 며칠동안 머물수 있는지 문자열로 나와있다.
• 각 무인도마다 머무를 수 있는 일수가 나와있고 바다를 건너지 않고 상하좌우 움직여서 최대한 며칠을 버틸 수 있는지 구하여라
• 배열로 생성하여 오름차순 하여라
• 문자열을 반복하면서 X 즉 바다가 아닌 무인도를 발견하고 visit 배열에 방문했는지 기록한다.
• 발견한 무인도의 상하좌우의 무인도가 방문했던 무인도인지 확인 후 방문하지 않았으면 큐에 해당 좌표를 넣고 visit 배열에 방문했다고 변경한다.
• 위 처럼 처음 발견된 무인도를 기준으로 더이상 발견되지 않을때까지 반복하면서 큐에 좌표를 넣고 최대 일수를 계속 더한다.
• 더이상 무인도가 발견되지 않으면 바다를 건너야하는 상황임으로 list에 최대 일수를 저장한다.

import java.util.*;
class Solution {
    public int[] solution(String[] maps) {
        int[] dx = {1,0,-1,0};
        int[] dy = {0,1,0,-1};
        boolean[][] visit = new boolean[maps.length][maps[0].length()];
        Queue<int[]> que = new LinkedList<>();
        List<Integer> list = new ArrayList();
        
        for(int i = 0; i<maps.length; i++){
            for(int j = 0; j<maps[i].length(); j++){
                if(visit[i][j] || maps[i].charAt(j) == 'X')    continue;
                
                visit[i][j] = true;
                que.add(new int[] {i, j});
                
                int sum = Integer.parseInt(maps[i].substring(j,j+1));
                
                while(!que.isEmpty()){
                    int len = que.size();
                    for(int q = 0; q<len; q++){
                        int[] temp = que.poll();
                        for(int k = 0; k<4; k++){
                            int x = temp[0] + dx[k];
                            int y = temp[1] + dy[k];
                            
                            // 좌표가 지도안에 존재하면서 방문하지 않은 무인도
                            if(x >= 0 && x < maps.length && y >= 0 && y < maps[0].length() 
                               && !visit[x][y] && maps[x].charAt(y) != 'X'){
                                visit[x][y] = true;
                                que.add(new int[] {x, y});
                                sum += Integer.parseInt(maps[x].substring(y,y+1));
                            }
                        }
                    }
                }
                
                list.add(sum);
            }
        }
        
        if(list.size() == 0){
            int[] result = {-1};
            return result;
        }
        
        int[] answer = new int[list.size()];
        for ( int i = 0; i<list.size(); i++ ) {
            answer[i] = list.get(i);
        }
        
        Arrays.sort(answer);
        
        return answer;
    }
}