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

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

dfs를 하며 값을 더해나가는 문제입니다. dfs 내부에서 temp를 만들어 값을 더해나가는 것을 떠올리는 데 시간이 많이 걸렸습니다.

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        ArrayList<Integer> temp = new ArrayList<>();
        int[][] intMaps = new int[maps.length][maps[0].length()];
        boolean[][] visited = new boolean[maps.length][maps[0].length()];
        
        buildIntMaps(maps, intMaps);
        
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                int cur = dfs(i, j, intMaps, visited);
                if (cur != 0) {
                    temp.add(cur);
                }
            }
        }
        
        if (temp.size() == 0) {
            return new int[] {-1};
        }
        
        Collections.sort(temp);
        int[] answer = new int[temp.size()];
        
        for (int i = 0; i < temp.size(); i++) {
            answer[i] = temp.get(i);
        }
        return answer;
    }        
    
    public int dfs(int i, int j, int[][] intMaps, boolean[][] visited) {
        int temp = intMaps[i][j];
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        if (visited[i][j] == true || intMaps[i][j] == 0) {
            return 0;
        }
        visited[i][j] = true;
        
        for (int c = 0; c < 4; c++) {
            int nx = i + dx[c];
            int ny = j + dy[c];
            
            if (nx >= 0 && nx < intMaps.length && ny >= 0 && ny < intMaps[0].length) {
                if (intMaps[nx][ny] != 0 && visited[nx][ny] != true) {
                    temp += dfs(nx, ny, intMaps, visited);
                }
            }
        }
        return temp;
    }
    
    public void buildIntMaps(String[] maps, int[][] intMaps) {
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                char cur = maps[i].charAt(j);
                if (cur == 'X') {
                    intMaps[i][j] = 0;
                    continue;
                }
                intMaps[i][j] = (int) cur - "0".charAt(0);
            }
        }
    }
}