[프로그래머스]무인도 여행 -JAVA

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

프로그래머스

 

 

문제만 봐도 대번에 느낄 수 있다..

이건 dfs or bfs다.

 

X가 아니고 방문하지 않은 곳을 큐에 넣고 상하좌우를 체크해서 다 더해주고

list에 넣어주면 될 것이다.

 

import java.util.*;
class Solution {
   static int[] dx = { 1, 0, 0, -1 };
    static int[] dy = { 0, 1, -1, 0 };

    public Integer[] solution(String[] maps) {
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        List<Integer> list = new ArrayList<>();
        bfs(maps, visited, list);
        Collections.sort(list);
        if(list.isEmpty()) return new Integer[]{-1};
        return list.toArray(new Integer[0]);
    }

    private void bfs(String[] maps, boolean[][] visited, List<Integer> list) {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                if (maps[i].charAt(j) != 'X' && !visited[i][j]) {
                    q.offer(new int[] { i, j });
                    visited[i][j] = true;
                    int sum = 0;

                    while (!q.isEmpty()) {
                        int[] xy = q.poll();
                        int cX = xy[0];
                        int cY = xy[1];
                        sum += Integer.valueOf(maps[cX].charAt(cY) + "");
                        for (int k = 0; k < 4; k++) {
                            int x = cX + dx[k];
                            int y = cY + dy[k];
                            if (x >= 0 && x < maps.length && 
                            y >= 0 && y < maps[0].length() && maps[x].charAt(y) != 'X'
                                    && !visited[x][y]) {
                                q.offer(new int[] { x, y });
                                visited[x][y] = true;
                            }
                        }
                    }
                    list.add(sum);
                }
            }
        }

    }

}