99클럽 코테 스터디 12일차 TIL - DFS

항해99 코테 스터디 12일차 문제인 프로그래머스의 '여행경로'는 주어진 티켓을 가지고 모든 도시를 순회하는 경로를 구하는 문제다. 난이도는 레벨3이며 DFS나 BFS를 통해 해결할 수 있다.

 

오늘의 문제 - 여행경로 문제 정보

문제 키워드

- DFS/BFS

난이도

- Level 3

 

문제 요약

• 티켓 정보(출발지-도착지)를 담은 배열이 주어진다.
• ICN(인천공항)에서 출발하여 모든 티켓을 사용해 모든 도시를 순회하는 경로를 구하여라.
  • 단, 정답이 여러개일 경우 사전순으로 더 빠른 경로를 선택해야 한다.

 

문제 풀이 과정  

• 티켓 정보를 그래프라고 생각하고, ICN에서 출발하여 사전순으로 더 빠른 티켓부터 사용해가며 도시를 순회한다.
  • 사전순으로 더 빠른 티켓부터 방문하기 위해, 각 출발지에 대한 도착지 리스트를 사전순으로 정렬하였다. 
  • 도시 순회는 DFS를 사용했다. 모든 도시를 방문하는 경우를 찾는 과정에는 BFS보다 DFS가 더 빠를 거라고 생각했기 때문이다.
• 모든 티켓을 사용한 경우에 정답을 저장한다.

코드

import java.util.*;
 
class Solution {
    
    private Map<String, List<Ticket>> ticketMap = new HashMap<>();
    private boolean[][] used;
    private List<String> answer;
    private boolean foundAnswer = false;
    
    public List<String> solution(String[][] tickets) {
        
        // 티켓 정보를 인접 리스트 맵으로 변경
        for(String[] ticket: tickets) {
            String s = ticket[0], d = ticket[1];
            ticketMap.putIfAbsent(s, new ArrayList<>());
            ticketMap.get(s).add(new Ticket(s, d));
        }
        
        // 각 인접 리스트를 알파벳순으로 정렬
        for(String key: ticketMap.keySet()) {
            Collections.sort(ticketMap.get(key));
        }
        
        // DFS를 이용해 경로 찾기
        List<String> route = new ArrayList<>();
        route.add("ICN");
        dfs(tickets.length, "ICN", route);
        
        return answer;
    }
    
    private void dfs(int N, String here, List<String> route) {
        // 가장 사전순으로 빠른 정답만 찾으면 되므로
        // 정답을 이미 찾은 경우에는 건너뜀
        if (foundAnswer) {
            return;
        }
        
        // N개의 티켓을 모두 사용한 경우 정답 저장
        if (route.size() == N+1) {
            answer = new ArrayList<>(route);
            foundAnswer = true;
            return;
        }
        
        // 현재 위치에서 사용 가능한 티켓을 사용하고 루트에 추가하여 다음 재귀에 들어감
        if (ticketMap.containsKey(here)) {
            for(Ticket ticket: ticketMap.get(here)) {
                if(!ticket.used) {
                    ticket.used = true;
                    route.add(ticket.dest);
                    dfs(N, ticket.dest, route);
                    ticket.used = false;
                    route.remove(route.size()-1);
                }
            }
        }
    }
    
    class Ticket implements Comparable<Ticket> {
        String source;
        String dest;
        boolean used = false;
        
        public Ticket(String source, String dest) {
            this.source = source;
            this.dest = dest;
        }
        
        @Override
        public int compareTo(Ticket other) {
            return this.dest.compareTo(other.dest);
        }
    }
}

• 시간복잡도: O(NlogN)
• 공간복잡도: O(N)