문제 링크

문제링크

문제 설명

제한 사항

입출력 예

입출력예는 링크 참조 ㅎ

풀이

1. 무조오오오오건 bfs인데 섬 체크만 해주면됨
2. 그냥 섬 하나당 bfs 한번 돌려서 더해놓은 값을 list에다 담자
3. list to array 해주면 끝!

코드

import java.util.*;
class Pos {
    int x, y;
    Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
class Solution {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    public int bfs(int startX, int startY, int width, int height) {
        int result = 0;
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(startX, startY));
        visited[startX][startY] = true;
        while(!q.isEmpty()) {
            Pos p = q.poll();
            int nx = p.x;
            int ny = p.y;
            result += map[nx][ny];
            
            for(int i = 0; i < 4; i++) {
                int nextx = nx + dx[i];
                int nexty = ny + dy[i];
                if(nextx < 0 || nextx >= height || nexty < 0 || nexty >= width)
                    continue;
                if(!visited[nextx][nexty] && map[nextx][nexty] > 0) {
                    visited[nextx][nexty] = true;
                    q.add(new Pos(nextx, nexty));
                }
            }
        }
        return result;
    }
    public int[] solution(String[] maps) {
        ArrayList<Integer> res = new ArrayList();
        int[] answer = {-1};
        map = new int[maps.length][maps[0].length()];
        visited = new boolean[map.length][map[0].length];
        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[0].length; j++) {
                if(maps[i].charAt(j) == 'X')
                    map[i][j] = 0;
                else
                    map[i][j] = maps[i].charAt(j) - 48;
            }
        }
        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[0].length; j++) {
                if(!visited[i][j] && map[i][j] > 0)
                    res.add(bfs(i, j, map[0].length, map.length));
            }
        }
        if(res.size() > 0) {
            answer = new int[res.size()];
            for(int i = 0; i < res.size(); i++)
                answer[i] = res.get(i);
            Arrays.sort(answer);
        }
        return answer;
    }
}