무인도 여행

사용 알고리즘: bfs

사용 언어: java

 

import java.util.*;

class Solution {
    static List<Integer> island = new ArrayList<>(); //섬의 크기 저장
    static int[] dx ={-1,1,0,0};
    static int[] dy ={0,0,-1,1};
    static boolean[][] visit;
    
    public int[] solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        
        island.add(-1);
        
        visit = new boolean[n][m];
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(!visit[i][j] && maps[i].charAt(j) != 'X') {
                    visit[i][j] = true;
                    bfs(i,j, maps, n,m);
                }
            }
        }
        
        if(island.size() > 1) island.remove(0);
        Collections.sort(island);
        return island.stream().mapToInt(Integer::intValue).toArray();
    }
    
    static void bfs(int x,int y, String[] maps, int n,int m) {
        int sum = maps[x].charAt(y) -'0';
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            
            for(int d=0; d<4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];
                
                if(nx>=0&&nx<n && ny>=0&&ny<m && maps[nx].charAt(ny) != 'X') {
                    if(!visit[nx][ny]) {
                        int val = maps[nx].charAt(ny) - '0';
                        sum += val;
                        visit[nx][ny] = true;
                        q.add(new int[] {nx, ny});
                    }
                }
            }
        }
        
        island.add(sum);
    }
}

 

 

전형적인 bfs 문제이고,

list를 array로 바꾸는 걸 잘 외우면 좋긴 하겠다.