프로그래머스 레벨2 무인도 여행(JAVA) dfs

자바

 

 

 

 

import java.util.*;

class Solution {
    int[][] map;
    List<Integer> answer = new LinkedList<>();
    public int[] solution(String[] maps) {
        
        map = new int[maps.length][maps[0].length()];
        // 2차원 배열로 정의
        for(int i = 0;i<maps.length;i++)
        {
            char[] mapCharArr = maps[i].toCharArray();
            
            for(int j = 0;j<mapCharArr.length;j++)
            {
                char c = mapCharArr[j];
                
                if(c == 'X' || c == 'x')
                {
                    //X표시면 -1리턴한다
                    map[i][j] = -1;
                }
                else
                {

                    // 문자열 c의 숫자에 문자열 0(아스키코드 48)을 빼준다. 예를 들어 1이면 49 - 48 = 1이 댄다.
                    map[i][j] = c - '0';
                }
            }    
        }
        
        for(int i = 0;i<map.length;i++)
        {
            for(int j = 0;j<map[0].length;j++)
            {
                int islandSum = dfs(i,j);
                if(islandSum > 0)
                {
                    answer.add(islandSum);
                    // 무인도 값 합치기
                }
            }
        }
        
        if(answer.size() == 0) return new int[] {-1};
        // 사이즈가 0, 전부 X면 -1 배열리턴
        Collections.sort(answer);
        // 값이 작은 것부터 나오게 출력
        int[] answerArr = new int[answer.size()];
        
        for(int i = 0;i<answerArr.length;i++) answerArr[i] = answer.get(i);
        // 배열에 집어넣기
        return answerArr;
    }
    
    public int dfs(int i, int j)
    {
        if(i<0 || j<0 || i>=map.length || j>=map[0].length) return 0;
        // 범위를 벗어나면 0리턴
        if(map[i][j] == -1) return 0;
        // 이미 탐색했거나 X표시면 0을 리턴
        int tmp = map[i][j];
        map[i][j] = -1;
        // 탐색했다.
        return tmp + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1);
        // 주변 무인도 값 탐색하기
    }
}

 

 

 

/// 리스트를 만들어서 add 해주고 X표시는 -1로 해서 if문으로 0보다 큰 거만 수집할 수 있게 한 뒤에 dfs를 활용한다.