[v2] 무인도 여행

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

 

일반적인 그래프 탐색 문제다.

 

import java.util.*;

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

        List<Integer> ans = new ArrayList<>();

        int R = maps.length;
        int C = maps[0].length();

        char[][] map = new char[R][C];
        boolean[][] vst = new boolean[R][C];

        int dr[] = {0,0,-1,1};
        int dc[] = {-1,1,0,0};

        for(int i=0; i<R; i++) {
            String s = maps[i];
            for(int j=0; j<C; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        Queue<int[]> q = new ArrayDeque();

        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {

                if(!vst[i][j] && map[i][j] != 'X') {

                    int val = map[i][j];
                    int cnt = 1;

                    q.offer(new int[]{i,j});
                    vst[i][j] = true;

                    while(!q.isEmpty()) {
                        int[] info = q.poll();
                        int r = info[0];
                        int c = info[1];

                        for(int t=0; t<4; t++) {

                            int tr = r + dr[t];
                            int tc = c + dc[t];

                            if(tr >= 0 && tr < R && tc >= 0 && tc < C && !vst[tr][tc] && map[tr][tc] != 'X') {
                                vst[tr][tc] = true;
                                val += map[tr][tc];
                                cnt++;

                                q.offer(new int[]{tr,tc});
                            }
                        }
                    }

                    ans.add(val - cnt * '0');
                }
            }
        }

        return ans.isEmpty()? new int[]{-1} : ans.stream().mapToInt(Integer::valueOf).sorted().toArray();
    }
}