[프로그래머스] 무인도 여행, 자바

문제         

프로그래머스

1 번째 시도   

dfs가 익숙치 않아 일단 제 생각대로 dfs를 짜보겠습니다.

 

import java.util.*;

class Solution {
    boolean[][] visited;
    
    public int[] solution(String[] maps) {
        visited =  new boolean[maps.length][maps[0].length()];
        ArrayList<Integer> resultList = new ArrayList<>();
        
        for(int i =0 ; i< maps.length; i++){
            for(int j =0; j< maps[0].length(); j++) {
                int count = 0;
                if(visited[i][j] == false) {
                    count = dfs(maps, i, j);
                    if(count != 0)
                        resultList.add(count);
                }
            }
        }
        
        Collections.sort(resultList);
        
       
        if(resultList.size() == 0) {
            int[] result = new int[1];
            result[0] = -1;
            return result;
        } else {
            int[] result = new int[resultList.size()];
            for(int i =0 ; i < resultList.size(); i++) {
                result[i] = resultList.get(i);
            }

            return result;
        }
    }
    
    public int dfs(String[] map, int index, int index2) {
        int count = 0;        
        if(index >= 0 && index < map.length && index2 >=0 && index2 < map[0].length() && visited[index][index2] == false && map[index].charAt(index2) != 'X'){
            visited[index][index2] = true;    
            count += Integer.parseInt(String.valueOf(map[index].charAt(index2)));
            
            dfs(map, index, index2+1);
            dfs(map, index, index2-1);
            dfs(map, index+1, index2);
            dfs(map, index-1, index2);
        }
        return count;
    }
}

역시나 dfs 로직에 문제가 있나봅니다.

2 번째 시도  

아주 사소한 실수였습니다. dfs 재귀호출만 하고 return 값을 받아주지 않고 있었습니다.

           dfs(map, index, index2+1);
            dfs(map, index, index2-1);
            dfs(map, index+1, index2);
            dfs(map, index-1, index2);

import java.util.*;

class Solution {
    boolean[][] visited;
    
    public int[] solution(String[] maps) {
        visited =  new boolean[maps.length][maps[0].length()];
        ArrayList<Integer> resultList = new ArrayList<>();
        
        for(int i =0 ; i< maps.length; i++){
            for(int j =0; j< maps[0].length(); j++) {
                int count = 0;
                if(visited[i][j] == false) {
                    count = dfs(maps, i, j);
                    if(count != 0)
                        resultList.add(count);
                }
            }
        }
        
        Collections.sort(resultList);
        
       
        if(resultList.size() == 0) {
            int[] result = new int[1];
            result[0] = -1;
            return result;
        } else {
            int[] result = new int[resultList.size()];
            for(int i =0 ; i < resultList.size(); i++) {
                result[i] = resultList.get(i);
            }

            return result;
        }
    }
    
    public int dfs(String[] map, int index, int index2) {
        int count = 0;        
        if(index >= 0 && index < map.length 
           && index2 >=0 && index2 < map[0].length() 
           && visited[index][index2] == false 
           && map[index].charAt(index2) != 'X') {
          
            visited[index][index2] = true;    
            count += Integer.parseInt(String.valueOf(map[index].charAt(index2)));
            
            count += dfs(map, index, index2+1);
            count += dfs(map, index, index2-1);
            count += dfs(map, index+1, index2);
            count += dfs(map, index-1, index2);
        }
        return count;
    }
}

 

 

꾸준히 코테를 준비한지 한 달 째가 됐는데 1000점을 넘긴 날이다. 이게 낮은지 높은지는 모르겠지만, 한 단계 위로 올라간 느낌이라 기분은 좋다!

 

아 그리고 다른 사람들의 풀이를 보다 알게된 사실이 있습니다. 저는 List 자료구조를 쓰다가 return 타입이 int 배열로 명시되어 있어 바꿔줬습니다. 근데 그럴 필요가 없습니다. 그냥 반환타입을 바꾸고 List를 return 해주면 됩니다.

 

import java.util.*;

class Solution {
    boolean[][] visited;
    
    public List<Integer> solution(String[] maps) {
        visited =  new boolean[maps.length][maps[0].length()];
        ArrayList<Integer> resultList = new ArrayList<>();
        
        for(int i =0 ; i< maps.length; i++){
            for(int j =0; j< maps[0].length(); j++) {
                int count = 0;
                if(visited[i][j] == false) {
                    count = dfs(maps, i, j);
                    if(count != 0)
                        resultList.add(count);
                }
            }
        }
        
        Collections.sort(resultList);
        
       
        if(resultList.size() == 0) {
             resultList.add(-1);
            return resultList;
        }else
            return resultList;
        
    }
    
    public int dfs(String[] map, int index, int index2) {
        int count = 0;        
        if(index >= 0 && index < map.length 
           && index2 >=0 && index2 < map[0].length() 
           && visited[index][index2] == false 
           && map[index].charAt(index2) != 'X') {
          
            visited[index][index2] = true;    
            count += Integer.parseInt(String.valueOf(map[index].charAt(index2)));
            
            count += dfs(map, index, index2+1);
            count += dfs(map, index, index2-1);
            count += dfs(map, index+1, index2);
            count += dfs(map, index-1, index2);
        }
        return count;
    }
}