[알고리즘] 프로그래머스 무인도여행 DFS 풀이 (자바,java)

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

프로그래머스

package Programmers;

import java.util.ArrayList;
import java.util.Arrays;

public class 무인도여행 {


    static String[][] myMaps;
    static String[][] chMaps;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};

    int sum = 0; //dfs돌때 더해질값

    public static void main(String[] args){
        무인도여행 T = new 무인도여행();
        String[] maps = {"X591X","X1X5X","X231X", "1XXX1"};

        T.solution(maps);

    }
    public int[] solution(String[] maps) {
        int[] answer = {};
        myMaps = new String[maps.length][maps[0].length()];
        chMaps = new String[maps.length][maps[0].length()];
        ArrayList<Node> loc = new ArrayList<>();
        ArrayList<Integer> tempAnswer = new ArrayList<Integer>();
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[0].length(); j++) {
                myMaps[i][j] = String.valueOf(maps[i].charAt(j));
                chMaps[i][j] = String.valueOf(maps[i].charAt(j));
                if(!String.valueOf(maps[i].charAt(j)).equals("X")){
                    //X가 아니면 좌표를 입력해서 저장하자.
                    loc.add(new Node(j, i));
                }
            }
        }
        for (int i = 0; i < loc.size(); i++) {
            Node tempLoc = loc.get(i);
            sum = 0;
            if(chMaps[tempLoc.y][tempLoc.x].equals("X")){
                //이미 왔다간 지점이면 스킵
                continue;
            }
            sum += Integer.parseInt(myMaps[tempLoc.y][tempLoc.x]); // dfs 시작점은 체크 안하니까 체크해줘야 한다.
            chMaps[tempLoc.y][tempLoc.x] = "X";
            dfs(tempLoc.x, tempLoc.y);
            tempAnswer.add(sum);
        }
        tempAnswer.sort(Comparable::compareTo);

        if(tempAnswer.size() > 0){ // tempAnswer 에 뭐라도 들었으면 answer에 답출력 없으면 -1 출력
            answer = new int[tempAnswer.size()];
            for (int i = 0; i < tempAnswer.size(); i++) {
                answer[i] = tempAnswer.get(i);
            }
        }else{
            answer = new int[1];
            answer[0] = -1;
        }
        return answer;
    }
    public void dfs(int x, int y){
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < myMaps[0].length && ny >= 0 && ny < myMaps.length && !chMaps[ny][nx].equals("X") && !myMaps[ny][nx].equals("X")){
                chMaps[ny][nx] = "X";
                sum += Integer.parseInt(myMaps[ny][nx]);
                dfs(nx, ny);
            }
        }
    }
}
class Node{
    int x;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
    int y;
}

 

DFS로 문제 해결했고 풀이는 

1. myMap과 chMap 을 활용 myMap 은 단순히 벽이 있는지 확인 chMap 은 왔던길체크 (지금보니 myMap은 없어도될듯?)

2. Loc 변수 List에 X가 아닐때 좌표를 미리 받아놓는다. (출발지점 정해주지 않기때문에) 

3. Loc에 저장된 좌표 지점을 하나씩 꺼내서 DFS 를 도는데 꺼냈을때 좌표가 chMaps에 X면 진행했던적이 있던거니까 스킵해준다.

4. 주르르르륵 돌면서 dfs가 끝나면 tempAnswer에 sum값을 집어 넣는다.

5. 모두다 X일수 있으니 tempAnswer 크기가 0이면 -1 을 담는다. 

끝.