문제

문제링크

접근

• 백트래킹 그림만 그려지면 금방 풀리는 문제이다.
• 방문 여부를 포함하고 있는 간선 클래스를 통해 <도시이름-간선리스트> 형태로 map을 구성하여 dfs, 백트래킹을 이어갔다.
• map을 사용할 때 항상 get이 null을 반환하는지를 조심하자!

풀이

import java.util.*;

class Solution {
    Map<String, List<Edge>> edges = new HashMap<>();
    Deque<String> stk = new ArrayDeque<>();
    int tCnt = 0;
    List<String> answer = null;
    
    public List<String> solution(String[][] tickets) {
        tCnt = tickets.length;
        
        for (String[] t : tickets) {
            if (!edges.containsKey(t[0])) edges.put(t[0], new LinkedList<>());
            edges.get(t[0]).add(new Edge(t[1]));
        }
        for (String key : edges.keySet()) Collections.sort(edges.get(key));
        
        dfs("ICN", 0);
        
        return answer;
    }
    
    public void dfs(String start, int depth) {
        if (answer != null) return;

        if (depth == tCnt) {
            answer = new LinkedList<>();
            answer.add("ICN");
            while(!stk.isEmpty()) answer.add(stk.removeLast());
            return;
        }
        
        if (!edges.containsKey(start)) return;
        for (Edge next : edges.get(start)) {
            if (next.visited) continue;
            next.visited = true;
            stk.push(next.end);
            
            dfs(next.end, depth + 1);
            if (answer != null) return;
            
            next.visited = false;
            stk.pop();
        }
        
    }
    
    class Edge implements Comparable<Edge>{
        String end;
        boolean visited = false;
        
        public Edge(String end) {
            this.end = end;
        }
        
        @Override
        public String toString() {
            return this.end;
        }
        
        @Override
        public int compareTo(Edge e) {
            return this.end.compareTo(e.end);
        }
    }
    
}