[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 여행경로

📚 문제 설명

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

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

 

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.

• 주어진 공항 수는 3개 이상 10,000개 이하입니다.

• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

• 주어진 항공권은 모두 사용해야 합니다.

• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.

• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

🎯 어떻게 풀었나

첫번째 시도 (50점/ 100점)

import java.util.ArrayList;
import java.util.TreeSet;
import java.util.HashMap;

class Solution {
    public String[] solution(String[][] tickets) {
        ArrayList<String> answer = new ArrayList<>();
        HashMap<String, TreeSet<String>> graph = new HashMap<>();
        int nTravel = tickets.length + 1; // 비행기 타는 횟수 =  티켓 개수 + 1
        String parent = "ICN";
        
        // init graph
        for(int i = 0; i < tickets.length; i++) {
            String from = tickets[i][0];
            String to = tickets[i][1];
            
            TreeSet<String> dest = (graph.containsKey(from)) ? graph.get(from) : new TreeSet<>();
            dest.add(to);
            graph.put(from, dest);
        }
        
        while(nTravel > 0)  {
            answer.add(parent);
            
            if(!(graph.containsKey(parent))) break;
            
            parent = graph.get(parent).pollFirst();
            nTravel--;
        }
                
        return answer.stream().toArray(String[]::new);
    }
}

 

두번째 시도 (50점/ 100점)

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.HashMap;

class Solution {
    public String[] solution(String[][] tickets) {
        ArrayList<String> answer = new ArrayList<>();
        HashMap<String, PriorityQueue<String>> graph = new HashMap<>();
        int nTravel = tickets.length + 1; // 비행기 타는 횟수 =  티켓 개수 + 1
        String parent = "ICN";
        
        // init graph
        for(int i = 0; i < tickets.length; i++) {
            String from = tickets[i][0];
            String to = tickets[i][1];
     
            PriorityQueue<String> dest = (graph.containsKey(from)) ? graph.get(from) : new PriorityQueue<>();
            dest.offer(to);
            graph.put(from, dest);
        }
        
        // System.out.println(graph); 
        
        while(nTravel > 0)  {
            answer.add(parent);
            
            if(!(graph.containsKey(parent))) break; 
            
            parent = graph.get(parent).poll();
            nTravel--;
        }
        
        // System.out.println(answer);
        
        return answer.stream().toArray(String[]::new);
    }
}

 

최종 코드

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public String[] solution(String[][] tickets) {
        Stack<String> temp = new Stack<>();
        boolean[] visited = new boolean[tickets.length];
        
        // 도착지 기준으로 정렬
        Arrays.sort(tickets, (o1, o2) -> o1[1].compareTo(o2[1]));
        
        // TEST
        // Arrays.stream(tickets).forEach(e -> System.out.println(e[0] + " -> " + e[1]));
        
        dfs(tickets, visited, temp, "ICN", 0);
        
        return temp.stream().toArray(String[]::new);
    }
    
    public boolean dfs(String[][] tickets, boolean[] visited, Stack<String> temp, String departure, int level) {
        temp.push(departure);
        
        if(level == tickets.length) return true; // 모든 항공권 사용하는 경로 찾음
        
        for(int i = 0; i < tickets.length; i++) {
            if(!visited[i] && tickets[i][0].equals(departure)) { // backtrack 
                visited[i] = true; // i번째 항공권 사용
                if(dfs(tickets, visited, temp, tickets[i][1], level + 1)) return true;
                visited[i] = false; // i번째 항공권 사용한 거 취소
            }
        }
        
        temp.pop();
        return false;
    }
}

 

🧐 왜 저렇게 풀었나

첫번째 시도 (50점/ 100점)

처음에는 이 문제를 굳이 DFS로 풀 필요가 없다고 생각했다.

Hashmap과 set을 이용해서 graph를 만든 후 표를 모두 사용할 때까지 경로를 찍으면 된다고 생각했기 때문이다. 이때 set으로는 TreeSet을 사용했는데 TreeSet은 내부적으로 BST를 사용하기 때문에 자동으로 정렬되기 때문이다. (사실 내부적으로 BST를 사용하는 것은 treeset이라는 명칭과 자동 정렬이라는 속성을 바탕으로 한 내 추측이다.)

그리고 처음에는 같은 항공권이 여러 장 있다는 생각을 못 해서 HashMap과 Set으로 그래프를 표현했다.

 

두번째 시도 (50점/ 100점)

같은 항공권이 여러 장 있다는 사실을 알게 된 후 중복을 허용하기 위해 TreeSet을 PriorityQueue로 바꿨다. 하지만 결과는 다르지 않았다.

 

최종 코드

반례를 도저히 생각나지 않았다. 그래서 다른 분들의 코드를 참고했다. 그 결과 backtracking을 사용하면 된다는 것을 알게 되었다.

더 자세히 말하면 tree의 depth가 항공권의 개수와 같은 경우 모든 항공권을 사용하여 여행을 한 것이기 때문에 우리가 찾는 경우이다. 그래서 이를 base case로 둔다.

그리고 DFS를 할 때는 항공권을 일일이 확인해서 출발지가 같고 아직 항공권을 사용하지 않은 경우 그 경로를 대상으로 DFS를 한다.

 

📖 무엇을 배웠나

Backtracking을 까먹고 있었는데 아래 블로그에서 설명을 잘 해주셔서 쉽게 이해할 수 있었다!

https://idea-sketch.tistory.com/29

[알고리즘] 되추적(Backtracking)을 알아보자.