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

안녕하세요, 스코리아입니다.

오늘은 자바(Java)의 DFS를 이용한 프로그래머스 Lv.3 여행 경로 문제를 풀어보겠습니다.

 

문제 설명

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

프로그래머스

입력값으로, tickets에는 항공권 정보가 2차원 배열로 담겨있습니다.

항상 "ICN" 공항에서 출발하고 주어지는 항공권을 모두 사용하여 방문할 수 있는 공항 경로를 return 하는 문제입니다.

• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미
• 주어지는 모든 항공권을 사용해야 함
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return

 

여기서 가장 중요한 키포인트는 가능한 경로가 여러 개일 경우 알파벳 순서가 앞서는 경로를 처리하는 로직을 어떻게 구현할 것인가입니다.

문제에 나와있는 예시도 살펴보겠습니다.

프로그래머스 문제 입출력 - 여행 경로

• 첫 번째 예시 : ICN부터 출발하여 JFK, HND, IAD 순서로 갑니다. 경로는 1가지입니다.
• 두 번째 예시 : ICN부터 출발하는데, ICN 출발지가 있는 ticket이 SFO, ATL 2개나 있습니다. SFO를 거쳐갈 경우, ATL, ICN, ATL, SFO가 나올 수 있습니다. ATL을 거쳐갈 경우, ICN, SFO, ATL, SFO 혹은 SFO, ATL, ICN, SFO
  • 즉 ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"], ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"], ["ICN", "ATL", "SFO", "ATL", "ICN", "SFO"] 3가지 경우가 나올 수 있습니다.
  • 여기서 알파벳 순서가 가장 앞서는 것은 2번째 것이기 때문에, 2번째것을 return 합니다.

 

풀이 과정

• currentRoute는 현재 들어 있는 경로들이 ArrayList 형태로 들어가 있습니다.
• visited는 방문 여부를 저장합니다. 한번 들린 ticket은 다시 재방문하지 않기 때문입니다.
• answer는 currentRoute 중 알파벳 순서가 가장 앞서는 것을 찾아 저장하고 최종 return 하는 용도입니다.

항상 ICN부터 출발하므로, 처음에 currentRoute에는 ICN값이 들어가 있어야 합니다.

 

dfs 함수에 대해서 자세히 살펴보겠습니다.

• tickets을 순차적으로 도는 for문: 해당 ticket을 방문하지 않았고, target(찾고 싶은 출발지)와 일치하는 ticket의 출발지(tickets[i][0])가 있는지 검사합니다.
  • 만약 일치하는 게 있다면, 해당 ticket의 visited 값을 true로 변경하고 currentRoute(현재 경로들) List에 해당 ticket의 도착지(tickets[i][1])를 추가합니다.
  • 그러고 나서 재귀적으로 호출하는데 이때 target은 ticket의 도착지(tickets[i][1])가 됩니다.
  • 모든 경로를 탐색하기 위해 재귀 호출 아래에, visited 값을 false로 바꿔주고 currentRoute의 마지막 값을 제거해 줍니다.
• currentRoute가 tickets의 길이만큼 다 찼을 경우 (처음에 ICN 추가해 줬으므로 currentRoute.size() -1): 
  • answer가 없다면(null) : answer는 currentRoute가 됩니다.
  • answer가 존재한다면 : answer.size() 만큼 for문을 돌려줍니다. (문제에서 '주어진 항공권은 모두 사용해야 합니다.'라고 하였으므로, currentRoute와 answer의 크기는 항상 같을 것입니다)
    • 현재 answer와 currentRoute가 일치하지 않을 때, answer가 currentRoute보다 뒤에 있다면(currentRoute가 answer보다 앞에 있다면) answer를 currentRoute로 교체해 줍니다. 그리고 answer와 currentRoute가 일치하지 않으면, 이후 부분은 계산할 필요가 없으므로 break로 빠져나가줍니다.

import java.util.*;

class Solution {
    List<String> currentRoute = new ArrayList<>();
    boolean[] visited;
    List<String> answer;
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        currentRoute.add("ICN");
        
        dfs(tickets, "ICN");
        return answer.toArray(new String[0]);
    }
    
    private void dfs(String[][] tickets, String target){
        if(currentRoute.size() - 1 == tickets.length){
            if(answer == null){
                answer = new ArrayList<>(currentRoute);
            }else{
                for(int i=0;i<answer.size();i++){
                    if (!answer.get(i).equals(currentRoute.get(i))) {
                        if (answer.get(i).compareTo(currentRoute.get(i)) > 0)
                            answer = new ArrayList<>(currentRoute);
                        break;
                    }
                }
            }
            return;
        }
        
        for(int i=0;i<tickets.length;i++){
            if(!visited[i] && tickets[i][0].equals(target)){
                visited[i] = true;
                currentRoute.add(tickets[i][1]);
                
                dfs(tickets, tickets[i][1]);
                
                visited[i] = false;
                currentRoute.remove(currentRoute.size()-1);
            }
        }
    }
}

 

실행결과

프로그래머스 문제 실행결과 - 여행 경로

• 모든 테스트 결과를 통과하였습니다.

---

 

지금까지 자바(Java) DFS를 이용한 프로그래머스 '여행 경로' 문제에 대해서 살펴보았습니다.

읽어주셔서, 감사합니다.