[Algorithm] 여행경로

목차

---

1. 문제 설명

2. 접근 방식

3. 코드

 

 

 

 

 

1. 문제 설명

---

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

프로그래머스

 

 

"ICN"에서 출발해 방문하는 모든 공항 경로를 출력하는 문제이다. 

이때 공항 수는 3개 이상 10,000개 이하이다. 

 

출발지	도착지
ICN	SFO
ICN	ATL

 

 

예제 2처럼 가능한 경로가 2개 이상인 경우엔 알파벳 순서가 앞서는 경로를 먼저 방문한다.

가능한 경로가 2개 이상이면 오름차순 정렬된 결과를 선택해야 한다는 의미로

위의 표를 기준으로 ATL을 먼저 방문해야 한다.

 

 

2. 접근 방식

---

방문 가능한 모든 경로를 만든 뒤, 가장 적합한 최적해를 고르는 방식으로 접근했다. 

출발지를 기준으로 가능한 목적지 리스트를 저장하는 graph가 필요하다고 생각했다. 

List<String>[] graph = new ArrayList[n];

 

n은 출발지 개수가 들어가야하는데...

주어진 공항 수는 3개 이상 10000개 이하로 무척 곤란한 크기가 된다. 

 

다음으로 떠올린 방법은 HashMap이였다.

Map<String, List<String>> graph = new HashMap<>();

 

물론 이렇게 구현하는 방법도 가능하다. 

1. 출발지 기준으로 목적지는 오름차순 정렬

2. 목적지 하나씩 뽑아서 dfs

 

 

하지만 코드가 꽤나 더럽다. 💀💀💀

▼ Dirty work

import java.util.*;

class Solution {
    public static Map<String, LinkedList<String>> graph;
    public static boolean[] visited;
    public static List<String> answer;
    
    public List<String> solution(String[][] tickets) {
        // 1. 출발지 - 목적지 기록
        graph = new HashMap<>();
        for(int i = 0; i < tickets.length; i++) {
            graph.computeIfAbsent(tickets[i][0], k -> new LinkedList<>()).add(tickets[i][1]);
        }
        
        // 2. value 기준 오름차순 정렬
        List<String> keys = new ArrayList<>(graph.keySet());
        for(String key : keys) {
            Collections.sort(graph.get(key));
        }
        
        // 3. dfs 호출
        List<String> path = new ArrayList<>();
        path.add("ICN");
        answer = new ArrayList<>();
        
        dfs("ICN", path, tickets);
        return answer;
    }
    
    public static boolean dfs(String now, List<String> path, String[][] tickets) {
        if(path.size() == tickets.length + 1) { // 다 방문
            answer.addAll(new ArrayList<>(path));
            return true;
        }
        
        if (!graph.containsKey(now)) return false;

        LinkedList<String> destinations = graph.get(now);
        for (int i = 0; i < destinations.size(); i++) {
            String next = destinations.remove(i); // 티켓 사용
            path.add(next);

            if (dfs(next, path, tickets)) return true;

            path.remove(path.size() - 1); // 백트래킹
            destinations.add(i, next);     // 티켓 복원
        }
        
        return false;
    }
}

 

💡💡 목적지 정렬과 graph 없이도 구현 가능한 방법이 있다. 💡💡

 

정렬을 먼저 하고 dfs를 호출하면 위의 코드처럼 로직이 복잡하지만

dfs를 먼저 호출하고 정렬을 나중에 해주는 방법도 가능하다.

 

정렬 시점이 문제의 핵심이다. 

① 먼저 ICN을 출발지로 시작해 가능한 경로라면 방문 표시를 해주고 다시 dfs를 호출한다. 

② 최적해가 아님을 고려하여 방문 표시를 제거한뒤 다시 경로를 탐색하는 로직도 필요하다. 

 

가능한 최종 경로를 리스트를 담고 리스트를 정렬하면,

가능한 경로가 2개 이상일 때 알파벳 순서대로 방문한 결과를 얻을  수 있다.

 

이때 이를 코드로 구현하면 다음과 같다.

 

 

 

3. 코드

---

import java.util.*;

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

 

now는 출발지를 의미한다.

무조건 "ICN"에서 출발하기 때문에 호출할 때 하드 코딩된 값을 넣어줬다.

path는 방문한 경로를 저장하는 값으로 출발지와 목적지 사이에 padding을 넣어 String 배열로 만들기 용이하게 해주었다. 

 

이처럼 dfs 마치고 정렬하믄, 비교적으로 간단하게 최적해를 구할 수 있다.