프로그래머스 Lv.2 무인도 여행 - JAVA

문제

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

 

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

 

 

풀이

해당 문제는 결국 상하좌우를 탐색하는 문제이고 백준에서도 많이 등장하던 풀이 유형이라 어렵지 않았지만.. 백준만 풀다보니 푸는 방식이 너무 어색했다. 백준이 입력값을 따로 주는 거 자체가 너무 좋은 거 같다.

해당 문제는 dx, dy배열을 만들어 상하좌우를 탐색하고 solution메소드에서 처음부터 탐색을 시작하는데 X가 아니어야면 bfs 메소드를 실행시킨다. 만약 X라면 bfs 메소드를 실행시키지 않는다. and 방문하지 않았던 노드여야만 bfs를 실행함

bfs는 탐색할 x,y 지점과 width와 heigh을 받아 실행한다.

bfs를 실행하고 해당 과정에서 X를 상하좌우에서 X가 아닌 곳을 모두 탐색한다. 그렇게 담은 데이터를 List에 추가하고

solution에서 해당 List를 비었을 경우 -1을 리턴하고 아닐 경우 int[]로 바꿔 return하는데 정렬이 필요하여 정렬해서 보내면 정답이다

import java.util.*;

class Solution {
    static char map[][];
    static boolean visited[][];
    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};
    static ArrayList<Integer> list = new ArrayList<>();
    
    public int[] solution(String[] maps) {
        visited = new boolean[maps.length][maps[0].length()];
        map = new char[maps.length][maps[0].length()];
       
        for(int a=0;a<maps.length ; a++){
            for(int i =0;i<maps[a].length();i++){
                map[a][i] = maps[a].charAt(i);
            }
        }
    
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[i].length;j++){
                if(!visited[i][j] && map[i][j] != 'X'){
                    
                    list.add(bfs(i,j,map.length,map[i].length));
                }
            }
        }
        int temp[] = list.stream()
                .mapToInt(Integer::intValue)
                .sorted()
                .toArray();
        
        return temp.length == 0 ? new int[]{-1} : temp;
    }
    
    static int bfs(int x,int y,int height,int width){
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x,y));
        visited[x][y] = true;
        int sum = 0;
        while(!queue.isEmpty()){
            Node now = queue.poll();
            
            sum += map[now.x][now.y] - '0';
            for(int i=0;i<4;i++){
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];
                
                if(nextX < 0 || nextY < 0 || nextX >= height || nextY >= width){
                    continue;
                }else{
                    if(!visited[nextX][nextY] && map[nextX][nextY] != 'X'){
                        queue.add(new Node(nextX,nextY));
                        visited[nextX][nextY] = true;                    
                    }
                }
            }
        }
        return sum;
    }
}

 class Node{
        int x;
        int y;
        public Node(int x,int y){
                this.x = x;
                this.y = y;
        }
}