[프로그래머스 Level 3] 여행경로

문제

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

프로그래머스

 

 

풀이

• 주어진 항공권을 모두 사용해서 여행경로를 짠다. 출발은 무조건 "ICN" 공항에서 한다.
• tickets의 각 행의 0번 인덱스는 출발 지역, 1번 인덱스는 도착 지역이다.
• 만약 두가지 이상의 여행경로가 나온다면 알파벳 순서가 앞서는 경로를 선택한다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

 

여행경로를 위해 주어진 항공권을 끝까지 탐색해야 하기 때문에 DFS를 사용해야 한다.

이때, 여러 경로가 나올 수 있기 때문에 boolean형 visited 배열을 사용해서 이미 방문한 여행지는 방문하지 않도록 한다.

 

DFS 함수의 매개변수는 항공권 개수를 파악해 재귀를 탈출할 수 있도록 하는 int형 depth와 현재 여행지와 여태 지나온 여행 경로, 그리고 tickets 배열로 한다.

depth와 tickets의 길이가 같아질 때, 모든 항공권을 탐색한 것이므로 여행 경로를 저장하고 재귀를 탈출한다.

 public void dfs(int depth, String now, String path, String[][] tickets){
	// depth: 깊이, now: 현재 여행지, path: 누적된 여행경로, tickets: 입력 배열
    if(depth == tickets.length){
     arrayList.add(path);
     return;
    }
 }

 

현재 여행지와 출발지가 일치하는 항공권이고, 방문하지 않았다면 그 항공권의 도착지를 now로 저장하고 다음으로 이동한다. 이때 여행 경로는 공백문자를 사이에 두고 현재까지의 경로 뒤에 연결한다. 해당 인덱스의 항공권은 visited 배열에서 true로 방문처리 하고, 재귀가 끝나고 돌아오는 시점에서 다시 false로 바꿔 다음에 방문할 수 있도록 한다.

 for(int i = 0; i < tickets.length; i++){
     if(!visited[i] && now.equals(tickets[i][0])){
         visited[i] = true;
         dfs(depth + 1, tickets[i][1], path + " " + tickets[i][1], tickets);
         visited[i] = false;
    }           
 }

 

 

여행 경로는 모두 ArrayList에 저장되고 Collections.sort()를 사용해 알파벳 순으로 정렬한다. 정렬된 ArrayList의 0번 인덱스가 알파벳이 제일 빠른 것이므로 이를 split()을 사용하여 출력 형식인 문자열 배열로 만들어 준다.

Collections.sort(arrayList);
String[] answer = arrayList.get(0).split("\\s");

 

 

전체 코드 (Java)

import java.util.*;

class Solution {
    static boolean visited[];
    static ArrayList<String> arrayList;
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        arrayList = new ArrayList<>();
        
        dfs(0, "ICN", "ICN", tickets);
        Collections.sort(arrayList);
        String[] answer = arrayList.get(0).split("\\s");
        return answer;
    }
    
     public void dfs(int depth, String now, String path, String[][] tickets){
         if(depth == tickets.length){
             arrayList.add(path);
             return;
         }
                  
         for(int i = 0; i < tickets.length; i++){
             if(!visited[i] && now.equals(tickets[i][0])){
                 visited[i] = true;
                 dfs(depth + 1, tickets[i][1], path + " " + tickets[i][1], tickets);
                 visited[i] = false;
            }           
         }
     }
}

 

 

후기

탈출 조건과 매개변수를 어떻게 사용할 지 고민할만한 문제였다. 알파벳 순으로 정렬하기 위해 arraylist를 사용하였는데 이 아이디어도 빠르게 생각하지 못했다.