프로그래머스 - 무인도 여행 (자바)

내가 보려고 쓰는 풀이.

 

 

문제 링크

 

 

[나의 풀이]

• 전형적인 DFS 문제라 생각했다.
• 근데 난 코딩테스트 찌랭이라(못해도 너무 못함), 내 풀이에 확신이 없었다.
• 다 풀고 남의 풀이들 보니, 역시나 DFS나 BFS로 푸는 게 일반적이었음.
• 전형적인 DFS인데도 불구하고 블로그에 기록하는 이유는, 글로 써야 내 머릿속에 한번 더 들어오기 때문.

import java.util.*;

class Solution {
    
    static char[][] map;
    static int row, col;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] check;
    static int sum = 0;
    
    public int[] solution(String[] maps) {
        int[] answer = {};
        row = maps.length;
        col = maps[0].length();
        
        map = new char[row][col];
        check = new boolean[row][col];
        for(int i = 0; i < row; i++) {
            String s = maps[i];
            for(int j = 0; j < col; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        
        ArrayList<Integer> result = new ArrayList<>();
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(map[i][j] != 'X' && check[i][j] == false) {
                    result.add(dfs(i, j));
                    sum = 0;
                }
            }
        }
        
        if(result.size() == 0) return new int[] {-1};
        
        answer = new int[result.size()];
        for(int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }
        Arrays.sort(answer);
        
        return answer;
    }
    
    public static int dfs(int startX, int startY) {
        check[startX][startY] = true;
        sum += map[startX][startY] - '0';
        
        for(int i = 0; i < 4; i++) {
            int x = startX + dx[i];
            int y = startY + dy[i];
            
            if(x < 0 || x >= row || y < 0 || y >= col) continue;
            
            if(map[x][y] != 'X' && check[x][y] == false) {
                dfs(x, y);
            }
        }
        
        return sum;
    }
}

1. maps를 char 배열인 map에다 저장한다.
2. 그래프 탐색을 한다.
   • X가 아닌 것이 나오면 무조건 숫자이므로, 탐색을 시작한다.
3. dfs 메서드
   • 먼저, 탐색을 위해 boolean을 true로 바꿔준다. (방문했던 곳 또 방문하지 않도록)
   • 전역변수로 선언한 sum에 탐색한 map 숫자들을 더한다.
   • 탐색이 끝나면 sum을 return 한다.
4. 계산된 sum은 ArrayList에 저장한다.
   • 배열의 개수가 몇 개인지 알아야 하고, 
   • 배열에 어떤 것이 들어가야 하는지 알아야 하기 때문.
5. sum은 다시 재활용해야 하기 때문에 sum = 0으로 다시 바꿔준다.
6. 만약 ArrayList의 size가 0이면 -1을 return 한다.
7. 아니면 answer 배열에 넣으면 된다.