프로그래머스) 무인도 여행 풀이 (Java)

 

학습 키워드: Java

 

154540 - 무인도 여행

1) 문제 설명 요약 (원문은 링크 참고):

 요약: 바다를 나타내는 문자 X, 섬에 있는 식량 나타내는 문자 1~9 를 담은 배열 maps에서 상하좌우로 이어진 숫자들을 하나의 섬으로 취급할 때, 섬에 있는 식량의 총 합을 계산하고 이를 오름차순으로 반환하는 문제입니다. 

 조건: 3 <= maps, maps[i] <= 100

 

 

2) 풀이 과정:

 예전에 언젠가 풀어본 스타일의 문제다. 배열을 순회하면서 방문한 위치를 마킹하고 방문하지 않은 섬을 찾아서 탐색하면서 방문 마킹을 해주고 합산한 식량 값을 기록하면 된다. 

 

 방문한 섬을 탐색하는 것을 재귀적으로 수행하는데, 배열을 순회할 때 visited[i][j] 값이 false인 숫자를 만난 경우 해당 위치부터 시작하여 상하좌우 index가 bound를 초과하지 않도록 주의하면서 값을 합산하여 그 합을 return 하도록 작성하면 된다.

 

 

3) 코드:

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private boolean[][] visited;
    private String[] maps;
    public int[] solution(String[] maps) {
        this.visited = new boolean[maps.length][maps[0].length()];
        this.maps = maps;
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                if (visited[i][j]) continue;
                int sum = explore(i, j);
                if (sum == 0) continue;
                list.add(sum);
            }
        }
        if (list.size() > 0) {
            int[] ret = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                ret[i] = list.get(i);
            }
            Arrays.sort(ret);
            return ret;
        }
        return new int[] {-1};
        
    }
    
    private int explore (int i, int j) {
        visited[i][j] = true;
        char cur = maps[i].charAt(j);
        if (cur == 'X') return 0;
        int sum = parseInt(cur);
        if (i - 1 >= 0 && !visited[i - 1][j]) sum += explore(i - 1, j);
        if (i + 1 < maps.length && !visited[i + 1][j]) sum += explore (i + 1, j);
        if (j - 1 >= 0 && !visited[i][j - 1]) sum += explore(i, j - 1);
        if (j + 1 < maps[i].length() && !visited[i][j + 1]) sum += explore(i, j + 1);
        return sum;
    }
    
    private int parseInt(char s) {
        return (int) s - 48;
    }
}