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

문제

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

프로그래머스

 

---

 

문제 개요

무인도에서 상, 하, 좌, 우로 연결된 땅들을 하나의 섬으로 간주하며, 각 섬의 식량 값을 모두 더해 해당 섬에서 머무를 수 있는 최대 일 수를 계산하는 문제입니다. 지도를 나타내는 문자열 배열이 주어지고, 숫자는 섬의 땅을, 'X'는 바다를 나타냅니다. 여러 섬의 최대 머무를 수 있는 일수를 계산하여 오름차순으로 정렬하여 반환합니다. 섬이 없다면 -1을 반환합니다.

접근 방법

1. 지도 초기화
   문자열 배열을 정수형 배열 map으로 변환하여 숫자는 해당 값을, 'X'는 0으로 설정합니다.
   이를 위해 makeMap 메서드를 사용하며, 숫자 변환 중 예외 처리로 'X'는 0으로 치환합니다.
2. 방문 여부 확인
   boolean[][] v를 통해 각 좌표의 방문 여부를 추적합니다. 처음엔 모든 좌표를 방문하지 않은 상태로 초기화합니다.
3. BFS로 섬 탐색
   bfs 메서드를 통해 시작점에서 상, 하, 좌, 우를 탐색하며 연결된 땅의 값을 합산합니다.
   • 큐를 이용하여 BFS를 구현하고, 방문한 좌표는 v 배열에 기록합니다.
   • 지도 범위를 벗어나거나 이미 방문한 곳, 값이 0인 곳은 탐색하지 않습니다.
   • 각 섬의 총 값을 반환합니다.
4. 섬의 총합 저장
   BFS 결과로 얻은 각 섬의 총합을 우선순위 큐(PriorityQueue)에 저장합니다.
   우선순위 큐를 사용해 결과를 자동으로 오름차순으로 정렬합니다.
5. 결과 반환
   • 큐의 크기가 0이면 섬이 없는 경우로 간주하고 [-1]을 반환합니다.
   • 큐의 값을 꺼내 배열로 변환해 결과로 반환합니다.

코드

import java.util.*;
class Solution {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1 ,1};
    static boolean[][] v;
    static int[][] map;

    public int[] solution(String[] maps) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        v = new boolean[maps.length][maps[0].length()];
        makeMap(maps);        
        
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                if(map[i][j] > 0 && !v[i][j]) {
                    v[i][j] = true;
                    int n = bfs(new Pos(i,j));
                    if(n > 0) pq.add(n);                    
                }
            }
        }
        
        int[] answer = new int[pq.size()];
        for(int i=0; i<answer.length; i++) answer[i] = pq.poll();
        return answer.length == 0 ? new int[]{-1} : answer;
    }
    
    public int bfs(Pos pos) {
        Queue<Pos> q = new LinkedList<>();
        q.add(pos);
        int sum = map[pos.r][pos.c];
        
        while(!q.isEmpty()) {
            Pos cur = q.poll();
            for(int i=0; i<4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                
                if(nr<0 || nc<0 || nr>=map.length || nc>=map[0].length || v[nr][nc] || map[nr][nc] == 0) continue;
                v[nr][nc] = true;
                sum += map[nr][nc];
                q.add(new Pos(nr, nc));
            }
        }
        
        return sum;
    }
    
    public void makeMap(String[] maps) {
        map = new int[maps.length][maps[0].length()];
        
        for(int i=0; i<map.length; i++) {
            String[] arr = maps[i].split("");
            for(int j=0; j<map[0].length; j++) {
                try {
                    int n = Integer.parseInt(arr[j]);
                    map[i][j] = n;
                } catch (NumberFormatException e) {
                    map[i][j] = 0;
                }
            }
        }
    }
    
    class Pos{
        int r, c;
        public Pos(int r, int c) {
            this.r = r;
            this.c = c;            
        }
    }
}