[프로그래머스 / DFS&BFS] 여행경로 (java) ⭐️

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

ticketsreturn

[[ICN, JFK], [HND, IAD], [JFK, HND]]	[ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]]	[ICN, ATL, ICN, SFO, ATL, SFO]

입출력 예 설명

예제 #1

[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.

예제 #2

[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.

 

 

[java]

어려웠다 ㅠ 다른 DFS 문제보다 .. 

그래서 다른 사람 풀이 보고함.

import java.util.*;
class Solution {
   static boolean visit[];
    static List<String> list = new ArrayList<>();
    static String route = "";
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        visit = new boolean[tickets.length];
        
        for(int i=0; i<tickets.length; i++){
        // 반복
            String departure = tickets[i][0];
            String destination = tickets[i][1];
            
            if(departure.equals("ICN")){
                visit[i] = true; // tic[i][0]이 기준
                route = departure + ","; //ICN
                dfs(tickets, destination, 1); 
                visit[i] = false; //다시 경로를 찾으려고
            }
        }
        Collections.sort(list);
        answer = list.get(0).split(",");
        
        return answer;
    }
    
    static void dfs(String[][] tickets, String end, int count){
        route += end + ",";
        
         if(count == tickets.length){
                list.add(route);
                return;
         }
         
        for(int i=0; i<tickets.length; i++){
            String depart = tickets[i][0];
            String desti = tickets[i][1];
            
            // 출발-도착 -> 출발-도착 로 이어진거 찾으려고 
            if(end.equals(depart) && !visit[i]){
                visit[i] = true;
                dfs(tickets, desti, count+1);
                visit[i] = false; // 다시 찾으려고
                route = route.substring(0, route.length()-4); //
            }
        }
    }
}

 

 

 

[참고]

https://youjourney.tistory.com/111

[프로그래머스] 여행경로 (java)(43164)

[링크]

https://programmers.co.kr/learn/courses/30/parts/12421

프로그래머스