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

링크

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

프로그래머스

 

설명

무인도의 각 칸 마다 먹을 수 있는 foodCnt가 있다. 

 

약간 유형은 석유 시추 문제와 비슷하게 각 칸 마다 BFS를 통해 갇혀진 칸 안에서 합계를 구하고,

이미 지나간 칸은 지나갔다고 마크해서 효율성을 최대화한다.

 

각 칸의 합계가 다 나왔다면 돌아가서 우선 순위 큐에 오름차순으로 Integer를 넣어주면 된다.

 

 

풀이

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        int r = maps.length;
        int c = maps[0].length();
        int[][] cells = new int[r][c];
        for(int i=0; i<r; i++) {
            String[] mapLine = maps[i].split("");
            for (int j=0; j<c; j++) {
                int cellFood = mapLine[j].equals("X") ? -1 : Integer.parseInt(mapLine[j]);
                cells[i][j] = cellFood;
            }
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0; i<r; i++) {
            // 각 칸 마다 bfs를 한다.
            for(int j=0; j<c; j++) {
                if (cells[i][j] < 1) {
                    continue;
                }
                
                int foodCount = bfs(cells, i, j, r, c);
                if (foodCount > 0) {
                    pq.add(foodCount);
                }
            }
        }
        
        if (pq.isEmpty()) {
            return new int[]{-1};
        }
        
        int[] answer = new int[pq.size()];
        int i=0;
        while(!pq.isEmpty()) {
            int foodCnt = pq.poll();
            answer[i] = foodCnt;
            i++;
        }
        
        return answer;
    }
    
    // 상, 하, 좌, 우
    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};
    private int bfs(int[][] cells, int sx, int sy, int r, int c) {     
        int foodCnt = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sx, sy});
        foodCnt = cells[sx][sy];
        cells[sx][sy] = 0;
        while(!q.isEmpty()) {
            int[] point = q.poll();
            int cx = point[0];
            int cy = point[1];
            for (int i=0; i<4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (nx >= 0 & nx < r && ny >= 0 && ny < c) {
                    if (cells[nx][ny] < 1) {
                        continue;
                    }
                    
                    q.add(new int[]{nx, ny});
                    foodCnt += cells[nx][ny];
                    cells[nx][ny] = 0;
                }
            }
        }
        return foodCnt;
    }
}