프로그래머스 DFS Level 3 (여행 경로)

문제

---

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

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

 

 

 

제한사항

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

 

 

풀이

---

DFS 로 해당 나라의 항공을 넣고 알파벳순으로 정렬한 뒤, 한 번 사용한 항공권은 다시사용할 수 없기 때문에 한번 간 나라는 삭제해주면서 했더니, 50점이 나왔다.

 

<50점 나온 코드>

import java.io.*;
import java.util.*;

class Solution {    

    boolean[] visited;
    List<String>[] flight_list;
    HashMap<String, Integer> map;
    List<String> result;
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        map = new HashMap<String, Integer>();        
        flight_list = new List[10000];
        result = new ArrayList<String>();
        
        for(int i = 0 ; i < 10000 ; i++){
            flight_list[i] = new ArrayList<String>();    
        }
        
        int idx = 0;
        for(int i = 0 ; i < tickets.length ; i++){
            if(!map.containsKey(tickets[i][0])){
                map.put(tickets[i][0], idx++);
            }
            
            if(!map.containsKey(tickets[i][1])){
                map.put(tickets[i][1], idx++);
            }
            
            flight_list[map.get(tickets[i][0])].add(tickets[i][1]);
        }
        
        visited = new boolean[idx];
        
        for(int i = 0 ; i < idx ; i++){
            Collections.sort(flight_list[i]);
        }
        
        String start = "ICN";
        dfs(start);
                
        
        answer = new String[result.size()];
        int i = 0;
        for(String country : result ){
            answer[i++] = country;
        }
        
        
        return answer;
    }
    
    public void dfs(String country){
        
        result.add(country);
        int now = map.get(country);       
        
        for(int i = 0 ; i < flight_list[now].size() ; i++){
            
            String next = flight_list[now].get(i);
            flight_list[now].remove(i);           
            
            dfs(next);     
        }
        
    }
}

 

문제점을 알아냈다.

모든 항공권을 사용해야 하지만 만약에

ICN HND

HND ICN

ICN ATL 

일경우 ICN 에서 갈수 있는 곳은 HND ATL 두곳이지만 문제에서 주문한 알파벳 순으로 방문을 하게 되면 

ICN - ATL 순으로 방문을 하지만 ATL 에서는 갈 곳이 없기 때문에 순환을 할 수 없는 구조가 된다.

따라서 이경우 ICN - HND- ICN - ATL 순으로 가야 모든 항공권을 사용할 수 있게 된다.

 

이러한 경우를 찾아 주어야한다.

 

List 에 티켓을 모두 사용하여 갈 수 있는 모든 경우의 수를 찾아준다.

그뒤 알파벳순으로 가장 빠른순으로 정렬한뒤 가장 빠른 것이 정답이 된다.

 

public void dfs(String[][] tickets, String now_Country, String course, int count){
        
    if(count == tickets.length){
        result.add(course);
        return;
    }
     
    for(int i = 0 ; i < tickets.length ; i++){
        if(!visited[i] && tickets[i][0].equals(now_Country)){
            visited[i] = true;
            dfs(tickets, tickets[i][1], course + " " + tickets[i][1], count + 1);
            visited[i] = false;
        }
    }
    
    return;
}

 

위의 DFS 코드와 같이 tickets.length 를 모두 사용한 경우엔 result 리스트에 넣어준다.

 

추후에 이를 정렬하여 가장 빠른 경로를 뽑아 낼 것이다.

이 그래프는 숫자가아니라 문자로 된 값을 가지고 있기 때문에 모든 ticket을 돌면서 확인해주는 방식을 사용하였다.

 

나머지는 기존의 DFS 코드와 유사하게 풀면된다.

 

이렇게 나온 result 리스트를 정렬하여 가장 빠른 경로를 뽑아내는 코드다.

Collections.sort(result);
        
answer = result.get(0).split(" ");

 

 

<전체 코드>

import java.io.*;
import java.util.*;

class Solution {    

    boolean[] visited;
    List<String>[] flight_list;
    List<String> result;
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        visited = new boolean[tickets.length];
        result = new ArrayList<String>();
        
        dfs(tickets, "ICN", "ICN", 0);
        
        Collections.sort(result);
        
        answer = result.get(0).split(" ");
        
        return answer;
    }
    
    public void dfs(String[][] tickets, String now_Country, String course, int count){
        
        if(count == tickets.length){
            result.add(course);
            return;
        }
        
        for(int i = 0 ; i < tickets.length ; i++){
            if(!visited[i] && tickets[i][0].equals(now_Country)){
                visited[i] = true;
                dfs(tickets, tickets[i][1], course + " " + tickets[i][1], count + 1);
                visited[i] = false;
            }
        }
        
        return;
    }
}