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

https://school.programmers.co.kr/learn/courses/30/lessons/154540?language=java

프로그래머스

---

◎ 문제

---

◎ 코드 및 풀이

import java.util.*;

public class Solution {
    static int X,Y,day;
    static int[] dx,dy;

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] result1 = sol.solution(new String[]{"X591X","X1X5X","X231X", "1XXX1"});
        int[] result2 = sol.solution(new String[]{"XXX","XXX","XXX"});
        System.out.println(sol.arrayEquals(result1,new int[]{1, 1, 27}) ? "테스트 통과" : "테스트 실패");
        System.out.println(sol.arrayEquals(result2,new int[]{-1}) ? "테스트 통과" : "테스트  실패");
    }

    public boolean arrayEquals(int[] a, int[] b){
        if(a.length!=b.length){
            return false;
        }
        for(int i=0; i<a.length; i++){
            if(a[i]!=b[i]){
                return false;
            }
        }
        return true;
    }

    public int[] solution(String[] maps) {
        int[] answer = {};
        /* 필요 자원 */
        Solution sol = new Solution();
        dx = new int[]{1,0,-1,0};
        dy = new int[]{0,1,0,-1};
        X = maps[0].length();
        Y = maps.length;
        day = 0;
        boolean[][] visited = new boolean[Y][X];
        int[][] map = new int[Y][X];

        for(int i=0;i<Y;i++){
            map[i] = maps[i].chars().map(c -> ((c > '0' && c <= '9') ? c - '0' : 0)).toArray();
        }

		//  DFS 실행 값 리스트에 추가
        List<Integer> days = new ArrayList<>();
        for(int i=0;i<Y;i++){
            for(int j=0;j<X;j++){
                if(!visited[i][j] && map[i][j]>0){
                    dfs(map, visited, j, i);
                    days.add(day);
                    day = 0;
                }
            }
        }
        
        // 섬이 존재하지 않아 비어있으면 -1 반환
        if(days.isEmpty()){
            return new int[]{-1};
        }

		// 리스트 오름차순 정렬
        Collections.sort(days);
        
        // 리스트 -> 배열
        answer = days.stream().mapToInt(d->d).toArray();

        return answer;
    }
    
    // DFS: 모든 경우의 값 구하기
    void dfs(int[][] map, boolean[][] visited, int x, int y){
        day += map[y][x];
        visited[y][x] = true;
        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || ny<0 || nx>=X || ny>=Y){
                continue;
            }

            if(!visited[ny][nx] && map[ny][nx]>0){
                dfs(map, visited, nx,ny);
            }
        }
    }
}

---

◎ 기록

가능한 모든 경우를 탐색하여 연결되어 있는 섬들의 값을 합한 결과를 구해야 하는 문제입니다.

해당 문제는 DFS, BFS 모두 해결 가능한 문제입니다.

다만, 최단거리가 필요하지 않고 연결 요소 전체를 탐색해야 하는 문제이기 때문에 DFS를 선택했습니다.