여행 경로

문제 정보

• 문제 링크
• 난이도: Lv.3
• 문제 유형: 탐색, DFS, 백트래킹

풀이

처음엔 DFS로 풀었는데, 그렇게 하면 테스트 케이스 1, 2번을 통과하지 못한다.

단순 DFS 풀이에 대한 반례는 다음과 같다.

tickets	return
[[“ICN”, “JFK”], [“ICN”, “JFK”], [“JFK”, “HND”], [“HND”, “ICN”], [“JFK”, “ATL”]]	[“ICN”, “JFK”, “HND”, “ICN”, “JFK”, “ATL”]
단순 DFS로는 [“ICN”, “JFK”, “ATL”]로 끝나버린다.

만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 라는 제한사항 때문에 알파벳 순서가 앞서는 티켓을 먼저 사용해야 하는데, 이 때문에 [“JFK”, “ATL”]를 먼저 사용하게 되면서 더 갈 수 있는 경로가 없기 때문이다.

그러나 이 경우 [“ICN”, “JFK”], [“JFK”, “HND”], [“HND”, “ICN”]을 사용하지 못한다.

때문에 “ATL”로 갔다가 티켓이 남아있는 경우 다시 되돌아오도록 해야한다.

즉, 백트래킹을 적용해야 한다는 뜻이다.

코드

import java.util.*;
 
class Solution {
    private boolean[] visited;
    private List<String> result = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        
        Arrays.sort(tickets, (a, b) -> a[1].compareTo(b[1]));
        
        dfs("ICN", "ICN", tickets, 0);
        
        return result.toArray(new String[0]);
    }
    
    private boolean dfs(String cur, String path, String[][] tickets, int count) {
        if (count == tickets.length) {
            result = Arrays.asList(path.split(" "));
            return true;
        }
        
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(cur)) {
                visited[i] = true;
            
                if (dfs(tickets[i][1], path + " " + tickets[i][1], tickets, count + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        
        return false;
    }       
}