[프로그래머스] 무인도 여행 Lv2 JAVA [탐색][엄탱]

문제 링크

프로그래머스

문제 설명

요약하자면, 지도에서 연결되어 있는 땅에 적혀있는 값을 더해 무인도에서 최대 며칠 동안 머물 수 있는지 알아보는 문제입니다. 

결괏값은 연결되어 있는 땅들의 합을 배열로 출력하면 됩니다.

해설

문제를 보면 이어져 있는 땅들의 합을 구해야 하기 때문에 DFS 혹은 BFS 탐색으로 총합을 쉽게 구할 수 있다고 판단된다.

특히 이문제는 DFS로 해도 상관없고 BFS로 해도 상관없어 보인다.
어떤 탐색을 사용하든 이어져 있는 땅들을 완전 탐색만 하는게 포인트라고 생각한다.

 

어떤 식으로 탐색을 했는지 살펴보자!

1. 우선 지도를 완전 탐색을 하여 처음부터 끝까지 반복문을 돌린다.
   • 한 번도 방문하지 않은 땅은 2번으로 넘어간다.
   • 방문한 땅이거나 바다(X)는 무시하고 지나간다.
2. 이제 방문 하지 않은 땅을 발견하게 되면 탐색을 돌려 이어져 있는 땅들의 합을 구하자
   • 중요한 건 이어져 있는 땅들은 방문했다는 표시를 남긴다.
3. 구한 합은 배열에 담아준다.
   • 배열이 비어있으면 배열에 -1을 담아 주고 반환
   • 배열이 비어있지 않으면 오름차순으로 정렬 후 반환

코드

import java.util.*;

class Solution {
    int[] X = {0, 0, 1, -1};
    int[] Y = {1, -1, 0, 0};
    
    public int[] solution(String[] maps) {
        List<Integer> list = new ArrayList<>();
        
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        
        for (int i = 0; i < maps.length; i++) {
            String map = maps[i];
            
            for (int j = 0; j < map.length(); j++) {
                if (maps[i].charAt(j) == 'X' || visited[i][j]) {
                    continue;
                }
                
                list.add(dfsForSum(i, j, maps, visited));
            }
        }
        
        if (list.size() == 0) {
            return new int[]{-1};
        }
        
        int[] answer = new int[list.size()];
        
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        
        Arrays.sort(answer);
        
        return answer;
    }
    
    private int dfsForSum(int x, int y, String[] maps, boolean[][] visited) {
        int sum = 0;        
        
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{x, y});
        
        while (!stack.isEmpty()) {
            int[] prev = stack.pop();
            
            int prevX = prev[0];
            int prevY = prev[1];
            
            
            if (visited[prevX][prevY]) {
                continue;
            }
            
            visited[prevX][prevY] = true;
            
            sum += maps[prevX].charAt(prevY) - '0';
            
            for (int i = 0; i < 4; i++) {
                int curX = X[i] + prevX;
                int curY = Y[i] + prevY;
                
                if (curX < 0 
                    || curY < 0 
                    || curX >= maps.length 
                    || curY >= maps[curX].length() 
                    || maps[curX].charAt(curY) == 'X' 
                    || visited[curX][curY]) {
                    
                    continue;
                }
                
                stack.push(new int[]{curX, curY});
            }
        }
        
        return sum;
    }
}