[프로그래머스][Java] 여행경로

[문제 링크]

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

프로그래머스

문제 설명

{출발공항, 도착공항} 

항상 "ICN"에서 출발해서 주어진 항공권을 모두 이용해서 여행 경로를 짠다.

가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 선택한다.

 

 

 

 

문제 풀이

• 백트래킹(DFS)

먼저 주어진 항공권에서 공항명을 알파벳 순서대로  정렬한다.

출발공항 기준으로 알파벳 순 정렬, 출발공항이 같으면 도착공항 기준으로 알파벳 순 정렬

→ 이렇게 하면 출발공항이 같고 도착공항이 다른 경로가 있을 경우, 알파벳 순서가 더 앞선 도착공항을 선택할 수 있다.

ex) {"ICN", "ATL"}, {"ICN", "SFO"}이 있으면 "ICN" →"ATL" 경로를 더 먼저 선택한다.

Arrays.sort(tickets, (str1, str2) -> {
    return str1[0].equals(str2[0]) ? str1[1].compareTo(str2[1]) : str1[0].compareTo(str2[0]);
});

 

"ICN"부터 시작해서 DFS 탐색을 통해 방문 가능한 여행 경로를 ArrayList path에 담는다.

path의 크기가 (티켓 수+1) 과 같아지면 방문 가능한 경로이다. → path의 경로를 answer 배열에 옮겨담는다.

이전에 알파벳 순서로 정렬을 했기 때문에 가장 먼저 찾은 가능한 경로가 정답이 된다.

따라서 그 이후에 찾은 가능한 경로는 찾을 필요가 없기 때문에 아래와 같이 answer 배열이 null이 아니면 return 한다.

if(answer[0] != null) return;

 

전체코드

import java.util.*;

class Solution {
    boolean[] visited;
    ArrayList<String> path = new ArrayList<>();
    String[] answer;
    
    public String[] solution(String[][] tickets) {
        
        visited = new boolean[tickets.length];
        answer = new String[tickets.length + 1];
        //출발 공항명 알파벳 순으로 정렬
        Arrays.sort(tickets, (str1, str2) -> {
            return str1[0].equals(str2[0]) ? str1[1].compareTo(str2[1]) : str1[0].compareTo(str2[0]);
        });

        dfs("ICN", tickets);
        
        return answer;
    }
    
    public void dfs(String departure, String[][] tickets) {
        path.add(departure);
        
        if(answer[0] != null) return;   //answer에 값이 들어있음 -> 이미 경로를 찾음
        
        if(path.size() == tickets.length + 1) { //
            for(int i = 0; i < answer.length; i++) {
            answer[i] = path.get(i);
            }
            return;
        }
        
        for(int i = 0; i < tickets.length; i++) {
            if(!visited[i] && tickets[i][0].equals(departure)) {
                visited[i] = true;
                dfs(tickets[i][1], tickets);
                path.remove(path.size() - 1);
                visited[i] = false;
            }   
        }
    }  
}

 

 

✔️ 체크

처음에는 정렬한 후 DFS 탐색에서 방문 가능한 경로 중 무조건 알파벳 순서가 앞선 곳을 고르면 된다고 생각했다.

이렇게 생각하고 풀었더니 제출 전 테스트 케이스에서는 통과를 했다.

하지만 {{"ICN", "BBB"}, {"ICN", "AAA"}, {"BBB", "ICN"}} 의 경우에 가능한 경로를 찾을 수 없다.

정렬하면 {{"BBB", "ICN"} , {"ICN", "AAA"}, {"ICN", "BBB"}}가 되는데, 알파벳 순서가 앞선 곳부터 고르면 "ICN" → "AAA" 에서 갈 곳이 없다.

생각해보면 당연한 내용인데 이 부분을 깨닫는 데 시간이 오래 걸렸다.