[JAVA] 프로그래머스 : 여행 경로 (코딩테스트 고득점 kit > 깊이/너비 우선 탐색(DFS/BFS))

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

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

DFS로 구현함

 

해결 방안

1. DFS를 이용하여 전체 여행 경로의 경우를 구하며 한가지의 경로를 String형의 route에 누적한 뒤 한가지 경로가 다 누적되면 routes에 추가함
=> 나중에 정렬을 쉽게 이용하기 위하여 String 값으로 저장

2. 목적지가 2가지 이상일 경우 알파벳 순이 되어야하므로 sort 정렬을 이용하여 routes를 정렬함

3. 정렬된 routes.get(0)이 답이 되고 String 값으로 저장하였으므로 answer의 String[] 형식에 맞게 파싱하여 저장해줌

 

코드

import java.util.*;
// 여행 경로
class Solution {
    public static String[] answer;
    public static String route;
    public static List<String> routes;
    public static boolean[] used;
    
    public static void dfs(String[][] tickets, String departure, String destination, int index){
        route += (destination + " ");
        
        if(index == tickets.length){
        	routes.add(route);
            //System.out.println(route);
            return;
        }

        // 도착지가 출발지가 되고 출발지인 모든 경우 DFS
        String start = destination;
        String nextDeparture;
        String nextDestination;
        for(int i=0; i<tickets.length; i++){
            nextDeparture = tickets[i][0];
            nextDestination = tickets[i][1];

            if(start.equals(nextDeparture) && used[i] == false){
                used[i] = true;
                dfs(tickets, nextDeparture, nextDestination, index+1);
                used[i] = false;
                // 전 단계로 초기화
                route = route.substring(0, route.length()-4);
            }
        }
            
        
    }
    
    public String[] solution(String[][] tickets) {
        System.out.println(tickets.length);
        answer = new String[tickets.length + 1];
        routes = new ArrayList<>();
        used = new boolean[tickets.length];
        
        for(int i=0; i<used.length; i++){
            used[i] = false;
        }
        
        String start = "ICN";
        String departure;
        String destination;
        for(int i=0; i<tickets.length; i++){
            departure = tickets[i][0];
            destination = tickets[i][1];
            
            // 첫 스타트가 ICN인 모든 경우 DFS 해서 routes에 저장
            if(start.equals(departure)){
                used[i] = true;
                route = departure + " ";
                dfs(tickets, departure, destination, 1);
                // dfs가 끝나고 나면 티켓은 다시 사용 안한 것으로 초기화
                used[i] = false;
            }
        }
        
        // 모든 경로 저장하고 String 오름차순
        Collections.sort(routes);
        
        //System.out.println("answer = " + routes.get(0));

        answer = routes.get(0).split(" ");
        
        return answer;
    }
}