Today I Learned

오늘은 DFS!

여행경로(DFS)

• 문제
  tickets 배열안에 있는 항공권을 다 써서 모든 공항을 다 순회하되 알파벳 순서가 빠른 루트만 반환하는 문제. 항상 ICN에서 출발해야한다.

• 실패한 풀이 과정
  다른 방법으로 풀어보고 싶어서 인접 배열과 리스트가 아니라 map으로 키값에 출발지, value에 treeset으로 도착지를 알파벳순으로 정렬되게 했다. 하지만 java.util.ConcurrentModificationException 가 발생해 성공하지 못하고 정석적인 풀이방법으로 돌아갔다. 이 부분은 추후에 한번 성공 가능하도록 수정해보려한다.

import java.util.*;
class Solution {
    private static List<String> answer;
    private static Map<String, TreeSet<String>> graph;
    // static boolean[] used;
    
    private static void dfs(String start){
        if (start.equals("ICN")) answer.add(start);
        TreeSet<String> ts = graph.get(start);
        if(ts == null) return;
        for(String dest : ts){
            graph.get(start).remove(dest);
            answer.add(dest);
            dfs(dest);
        }
    }
    
    public String[] solution(String[][] tickets) {
        answer = new ArrayList<String>();
        
        // 간선 생성
        graph = new HashMap<String, TreeSet<String>>();
        for(String[] ticket : tickets){
            String starting = ticket[0];
            String destination = ticket[1];
            
            graph.putIfAbsent(starting, new TreeSet<String>());
            graph.get(starting).add(destination);
        }
        
        dfs("ICN");
        String[] ans = answer.toArray(new String[answer.size()]);
        return ans;
    }
}

• 성공한 풀이과정

1. 정석대로 일단 visited 체크하는 boolean 배열을 만들고 모든 루트를 저장하는 list를 하나 만들었다. 간선화 작업은 필요없어서 그냥 tickets 배열을 바로 썼다.

2. 여행 루트를 쭈욱 끝까지 들어가서 그 루트를 저장해두고 비교하는 방식으로 풀어야하므로 DFS를 적용했다. DFS는 재귀로 구성했다.

3. dfs함수의 매개변수는 시작공항, 루트, 카운트와 티켓정보를 받는다. 아직 방문하지 않았고, 시작공항이 겹치는 티켓의 경우만 방문 처리후 재귀로 다시 깊게 루트를 파고든다. 카운트가 티켓의 숫자만큼 체크되면(다 돌았으면) 저장한 루트를 루트 리스트에 넣는다. 루트는 띄어쓰기를 기준으로 계속 붙는 구조다.

4. 마지막단계에서 루트들이 모인 리스트를 sort해서 알파벳순으로 가장 빠른 루트를 찾고, 여기서 가장 첫 값을 .split(" ")으로 분리해 배열로 반환하면 끝.

• 구현 코드

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