[Java] 여행경로

1. 문제

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

코딩테스트 연습 - 여행경로

 

 

 

2. 풀이과정

dfs문제 + 문자열 정렬

 

1) 문자열을 정렬하기 위해서 지역 이름들을 하나의 문자열로 concat해서 사용

2) 사전순 정렬

3) 공항 이름이 모두 3자리이므로, 3개씩 잘라서 배열에 담아서 반환

 

import java.util.*;

class Solution {
    static int N;
    static ArrayList<String> result;
    
    public static void dfs(String[][] tickets, String s, boolean[] v, String route, int cnt){
        if(cnt==N){
            result.add(route);
            return;
        }
        
        for(int i=0; i<N; i++){
            if(tickets[i][0].compareTo(s)==0 && !v[i]){
                v[i] = true;
                String temp = new String(route);
                dfs(tickets, tickets[i][1], v, route.concat(tickets[i][1]), cnt+1);
                route = temp;
                v[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        N = tickets.length;
        String[] answer = new String[tickets.length+1];
        result = new ArrayList<>();
        dfs(tickets, "ICN", new boolean[N], "ICN", 0);
        //답이 여러 개면, 사전 순에서 첫 번째 반환
        Collections.sort(result);
        int size = result.get(0).length();
        for(int i=0; i<size; i+=3){
            answer[i/3]=result.get(0).substring(i, i+3);
        }
        return answer;
    }
}