문제링크

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

구현방법

BFS 알고리즘이 생각남 -> 탐색 문제

방문체크를 통해서 중복적으로 발생하는 걸 막는다. 돌고 난 값은 따로 저장

-> X를 0으로 치환

만약 방문을 했거나 0인경우는 제외하고 진행한다.

제외한 나머지상황인경우

-> 탐색해서 값을 우선순위큐에 담아두고 만약 우선순위 큐에 값이 없는 경우

-> -1을 담은 배열을 리턴

-> 우선순위큐에 값이 담겨져있는경우 그 값을 뽑아서 배열로 리턴

구현알고리즘

탐색(BFS) 알고리즘

CODE

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;



class Solution {

    int map[][];

    boolean visited[][];

    PriorityQueue<Integer> island = new PriorityQueue<>();

    int N;
    int M;

    int dx[] = {0,-1,0,1};
    int dy[] = {-1,0,1,0};

    public int[] solution(String[] maps) {

        N = maps.length;
        M = maps[0].length();


        map = new int[N][M];
        visited= new boolean[N][M];

        for (int row = 0; row < N; row++) {

            for(int col = 0; col < M; col++){
                char ch = maps[row].charAt(col);
                //X를 0으로 치환
                if(ch == 'X'){
                    continue;
                }
                map[row][col] = ch - '0' ;
            }
        }

        for(int row =0 ; row < N;row++)
        {
            for(int col = 0; col <M;col++){
                //방문 했던곳이거나 0인경우 제외
                if(!visited[row][col] && map[row][col] != 0){
                    checkIslandSize(row,col);
                }
            }
        }

        if(island.isEmpty()){
            return new int[]{-1};
        }
        int answer[] = new int[island.size()];
        for(int idx=0;idx <answer.length;idx++){
            answer[idx]= island.poll();
        }

        return answer;
    }

    private void checkIslandSize(int row, int col) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{row,col});
        visited[row][col] = true;
        int size = 0;
        size += map[row][col];

        while(!que.isEmpty()){
            int[] cur = que.poll();

            for(int idx =0; idx < 4;idx++){
                int nt_row = cur[0] + dx[idx];
                int nt_col = cur[1] + dy[idx];

                //범위를 벗어나거나 이미 방문한경우 갈수 없는경우 제외
                if(nt_row < 0 || nt_row >= N || nt_col < 0 || nt_col >= M || visited[nt_row][nt_col] || map[nt_row][nt_col] == 0)
                    continue;

                if(!visited[nt_row][nt_col]){
                    visited[nt_row][nt_col] = true;
                    size+= map[nt_row][nt_col];
                    que.offer(new int[]{nt_row,nt_col});
                }
            }

        }


      
        island.offer(size);
    }
}