[프로그래머스,Java] Level3 : 여행 경로

 

 

문제분석

 

문제목표:    티켓을 전부 사용하여  여행경로를 구해주세요

 

단, 중복된 여행경로가있을경우  알파벳순서가 앞서는 경로를 우선하라.

 

 

 

일반적인 DFS를 작성하는법을 기본으로 알아야하고,

추가로 생각해야하는 경우는  중복된 여행경로가 있을경우 알파벳 순서가 앞서는 경로를 우선하라 이다.

 

보통 우선하라 =  정렬 이다.

 

정렬을 하려면  sorting을 해야하는데   

필자는 경로를 모두 String으로 작성한뒤

sorting을하고 3글자씩 자르기로했다.

 

 

 

dfs()의  탈출조건과, 백트래킹이다.

 

백트래킹에대해 조금 더 분석하자면,  

 

dfs를 진행할때마다  출발지점 start, 깊이 level , 여행경로 path를 갱신해줘야한다.

 

 

따라서 탈출조건은 level이 티켓+1 이면 모든 경로를 돌은것이므로, 

 

경로를 저장하고  반환한다.

 

경로를 모아둔 results를 한번 정리하고,  제일 알파벳이 적은 값을 하나가져온뒤

 

3단어씩 일정하게 잘라준다.   

 

문제를 보면 공항의 단어는 3글자로 일정하므로,  가능한 로직이다.

 

문제풀이

 

import java.util.*;
class Solution {
    
boolean[] visited;
 
List<String> results = new ArrayList<>();
 
    public String[] solution(String[][] tickets) {
        String[] answer = new String[tickets.length+1];
        
        
        visited =new boolean[tickets.length];
        
        dfs(tickets,"ICN",1,"ICN");
        
        Collections.sort(results);
        
        String result = results.get(0);
        
        for(int i=0;i<=tickets.length;i++){
            answer[i]=result.substring(3*i,3*i+3);
        }
    
    
        return answer;
    }
    
    public void dfs(String[][] tickets, String start,int level,String path){
        
         //모든 경로를 돌면 저장                   
                if(level==tickets.length+1){
                    results.add(path);
                    return;
                }
        
        for(int i=0;i<tickets.length;i++){
            if(tickets[i][0].equals(start)&&!visited[i]){
                visited[i]=true;
                
                dfs(tickets,tickets[i][1],level+1,path+tickets[i][1]);
               
                visited[i]=false;
            }
        }
       
        
    }
}