[프로그래머스] 여행 경로(DFS 풀이)

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

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

문제 설명

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

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

제한사항

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

풀이

처음 문제를 보고, 다음과 같은 알고리즘을 생각하여 코드를 짰다.

 

tickets 배열을 사전 순으로 정렬하여, 맨 앞 index 부터 경로를 탐색하면..

사전 순으로 가장 앞서는 경로를 얻어 낼 수 있지 않을까?

 

위와 같은 생각으로, 모든 경로를 탐색하지 않고 가장 앞선 index의 경로만 탐색하도록 하여 제출하였다.

그런데 1, 2번에서 런타임 에러가 났다..

 

곰곰히 생각해 보니, 아래와 같은 경우에는 위 알고리즘이 정상적으로 동작하지 않는다.

 

tickets : [ [ "ICN", "AME" ], [ "ICN', "BZL" ], [ "BZL", "ICN" ] ]

일 때,

정렬된 tickets 배열 = [ [ "BZL", "ICN"], ["ICN", "AME"], ["ICN", "BZL"] ] 이다.

 

위 정렬된 tickets 배열에서 "ICN" 공항으로부터 출발하여 앞서는 idx부터 경로를 탐색하면,

["ICN", "AME"]를 탐색하게 된다.

그런데 이런 경우, "AME"에서 출발하는 TICKET 이 존재하지 않으므로, 모든 티켓을 사용할 수 없다.

 

따라서, 모든 가능한 경로를 탐색한 후 알파벳 순으로 앞서는 경로를 return 해야한다.

import java.util.*;

/*
1. 사전 순으로 가장 앞서는 경로를 return 하기 위해 tickets 를 먼저 정렬함
2. ICN 부터 시작하여 정렬된 tickets를 돌면서 경로를 반환함.
*/

/*
위와 같이 문제를 풀었을 때, 알파벳 순으로 앞서는 경로만을 탐색함..
그런데, 알파벳 순으로 앞서는 경로로 갔을 때 주어진 항공권을 모두 사용하지 못하는 경우의 수가 존재할 수 있음.
따라서, 알파벳 순으로 앞서는 경로 뿐만 아니라.. 모든 경로를 탐색한 후 순서가 앞서는 경로를 return 해야함.
*/

class Solution {
    
    public boolean visited[];
    public ArrayList<String> pathList = new ArrayList<>();
    
    public void DFS(String departure, int depth, String[][] tickets, String nowPath){
        
        if(depth == tickets.length){
            pathList.add(nowPath);
            return;
        }
        
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals(departure) && !visited[i]){
                visited[i] = true;
                DFS(tickets[i][1], depth+1, tickets, nowPath + tickets[i][1]);
                visited[i] = false;
            }
        }
        return;
        
    }
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        // 최초에 생각한 알고리즘 - 그냥 tickets를 알파벳 순서대로 정렬하여 앞서는 경로만을 탐색한다.
//         Arrays.sort(tickets, (a, b) ->{
            
//             String tmp1 = a[0] + a[1];
//             String tmp2 = b[0] + b[1];
            
//             return tmp1.compareTo(tmp2);
//         } );
        
        visited = new boolean[tickets.length];
        
        DFS("ICN", 0, tickets, "ICN");
        
        Collections.sort(pathList);
   
        answer = new String[tickets.length + 1];
    
        for(int i=0; i<tickets.length+1; i++){
            answer[i] = pathList.get(0).substring(i*3, i*3 + 3);
        }
        
        return answer;
    }
}

 

추가

해당 문제를 BFS 로도 풀어보고 싶어서 고민해봤는데..

BFS는 애초에 최적 경로 1개만을 return 하는 구조이므로, 여러 개의 최적경로를 구해 사전 순으로 앞서는 경로를 return 해야하는 문제 특성 상 BFS 로는 풀 수 없을 것 같다는 생각이다.

BFS로 푸신 분들의 풀이를 찾아봤으나.. 찾지 못했다.

BFS로 푸신 분들이 있다면.. 댓글로 코드 공유 부탁드립니다.