[자바] 프로그래머스 여행경로

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

프로그래머스

 

크아악.. 이 문제도 정렬해야되는 것만 아니었으면 맞을 수 있었는데 정렬해야되는 사실을 테스트케이스 돌려보다가 알았다.. 근데 어떤 식으로 정렬해야 내부의 배열에 영향을 주지 않고 정렬한 뒤에 이 값을 출력해낼 수 있을지에 대해서 고민하다가 결국 또 구글링행 ^^

 

dfs 함수를 만들 때 문자열을 원소로 갖는 ArrayList를 생성하여 이를 정렬하게 되면 오름차순에서 가장 앞에 있는 문자열을 답으로 도출해내면 된다. 그렇기 때문에 매개변수에 시작점과 다음 나라를 가리키는 nation과 이미 지나온 경로인 route를 입력 받아서 함수 내부로 진입한다. 

 

함수 내부에서는 cnt 값과 ticket의 길이가 같을 때 가능한 모든 경로를 저장하도록 하여, 현재의 route를 저장하게 하고 return한다. 그리고 for문으로 tickets를 돌면서 만약 nation과 tickets[i][0]이 동일한지 그리고 visited[i]는 false인지 확인한 뒤에 조건에 만족한다면 true로 변경하고 dfs 내에 또 route+ " " + tickets[i][1] 로 다음 목적지를 작성해준다. 그리고 dfs 함수를 부른 다음 줄에는 visited를 다시 false로 만들어주며 모든 경우에 대해서 확인해보도록 한다. 

 

함수에서 탈출하게 되면 Collections.sort로 문자열을 오름차순 정렬하게 되고, 그 중 가장 앞의 문자열을 뽑아서 " "를 기준으로 split하여 answer에 저장하면 원하는 대로 출력할 수 있다.

 

import java.util.*;

class Solution {
    public static boolean[] visited;
    public static ArrayList<String> arr = new ArrayList<>();
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        visited = new boolean[tickets.length];
        dfs(tickets, "ICN", "ICN", 0);
        
        Collections.sort(arr);
        answer = arr.get(0).split(" ");
        return answer;
    }
    
    public static void dfs(String[][] tickets, String route, String nation, int cnt){
        if(cnt == tickets.length){
            arr.add(route);
            return;
        }
        
        for(int i = 0; i < tickets.length; i++){
            if(tickets[i][0].equals(nation) && !visited[i]){
                visited[i] = true;
                dfs(tickets, route + " " + tickets[i][1], tickets[i][1], cnt+1);
                visited[i] = false;
            }
        }
    }
}