문제 - 무인도 여행

문제접근

단순 bfs를 사용하여 각 연결되어 있는 섬들의 값들을 합산하여 배열을 오름차순으로 정렬해주고 결과를 출력하면 된다.

import java.util.*;

class Solution {
    int dx[] = {1,0,-1,0};
    int dy[] = {0,1,0,-1};
    public int[] solution(String[] maps) {
        ArrayList<Integer> lists = new ArrayList<>();
        int x = maps.length;
        int y = maps[0].length();
        boolean visited[][] = new boolean[x][y];
        int board[][] = new int[x][y];
        for(int i=0;i<x;i++)
        {
            String temp[] = maps[i].split("");
            for(int j=0;j<temp.length;j++)
            {
                if("X".equals(temp[j]))
                {
                    board[i][j] = -1;
                }else
                    board[i][j] = Integer.parseInt(temp[j]);
            }
        }
        
        //bfs
        for(int i=0;i<x;i++)
        {
            for(int j=0;j<y;j++)
            {
                if(board[i][j] != -1 && !visited[i][j])
                {
                    Queue <int []> q = new LinkedList<>();
                    q.add(new int[]{i,j});
                    visited[i][j] = true;
                    int count = board[i][j];
                    while(!q.isEmpty())
                    {
                        int cnt[] = q.poll();
                        
                        for(int d=0;d<4;d++)
                        {
                            int nx = cnt[0] + dx[d];
                            int ny = cnt[1] + dy[d];
                            
                            if(0<=nx && nx < x && 0<= ny && ny < y)
                            {
                                if(!visited[nx][ny] && board[nx][ny] != -1)
                                {
                                    q.offer(new int[]{nx,ny});
                                    count+=board[nx][ny];
                                    visited[nx][ny] = true;
                                }
                            }
                        }
                    }
                    
                    lists.add(count);
                }
            }
        }
        if(lists.size() == 0)
        {
            return new int[]{-1};
        }
        Collections.sort(lists);
        int []answer = new int[lists.size()];
        for(int i=0;i<lists.size();i++)
        {
            answer[i] = lists.get(i);
        }
        return answer;
    }
}