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

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

 

 

아직 실력이 부족하여 풀이가 아주그냥 엉망진창이다.

 

하지만 구현 하고자 하는 의도는 명확했다;;

• dfs를 이용하여 순회
• 순회하다가 더이상 나아갈 곳이 없으면 돌아오면서 누적합을 구한다.
• 이렇게 구한 누적합을 큐에 저장한다.
• 큐에 있는 값들을 정수 배열에 넣고 정렬 후 반환

개인적으로 이 문제에서 가장 중요하면서 어려웠던 부분은 돌아오면서 누적합을 구하는 과정이라고 생각한다.

 

<정답 코드>

import java.util.*;
class Solution {
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static   Queue<Integer> queue = new LinkedList<>(); // 각 순회에서 얻은 정답을 저장
    public static boolean[][] visit; //방문여부 기록

    public int[] solution(String[] maps) {
     
        visit = new boolean[maps.length][maps[0].length()];
        boolean check=false; //모든 값이 다 X일 경우를 체크
        
        for(int i=0; i<maps.length; i++){
            for(int j=0; j<maps[0].length(); j++){
                if(maps[i].charAt(j)!='X' && !visit[i][j]){
                    int x = dfs(i,j,maps); //순회 시작
                    queue.add(x); //한 순회에서 구한 누적합 큐에 저장 
                    check=true;
                }
                 visit[i][j]=true;
            }
        }
        if(check==false){ //모든 값이 다 X인 경우
            int[] answer = new int[1];
            answer[0]=-1;
            return answer;
        }
        
        int[] answer= new int[queue.size()];
        for(int i=0; i<answer.length; i++){
            answer[i]=queue.poll(); //큐에 있는 값을 배열에 저장
        }
        Arrays.sort(answer); //오름차순 정렬
        return answer;
    }
    public int dfs(int a, int b, String[] maps){ //a = 위아래, b = 좌우
        
        visit[a][b]=true; //방문 여부를 기록하여 중복 방문 방지
        int c=0; 
        boolean check=false; //뒤로 더 갈곳이 있는지 없는지 체크
        for(int i=0; i<4; i++){
            int current_a=a+dx[i];
            int current_b=b+dy[i];
            if(current_a>=0 && current_a<maps.length && current_b>=0 && current_b<maps[0].length()){
            if(maps[current_a].charAt(current_b) != 'X' && !visit[current_a][current_b]){
                 c = c + dfs(current_a,current_b,maps);
                check=true;
            }
            }
        }
        if(check==false){
            return Integer.parseInt(String.valueOf(maps[a].charAt(b))); //만약 갈곳이 없으면 현재 위치의 값을 반환
        }
        
        else{
            return c+Integer.parseInt(String.valueOf(maps[a].charAt(b))); //현재 위치에서 방문한 곳이 있다면 누적합을 반환
        }
    }
}