여행경로 [자바]

 

🧫 문제 분석

✔️ 출처

여행경로 level 3

📖 문제

 

 

모든 경로를 탐색해서 사전순으로 앞서는지 확인하는 문제

 

간과한 것은 같은 경로가 여러개 있을 수 있다는 것이다. 

ICN -> SFO, ICN -> SFO 이렇게 같은 경로가 여러개로 입력될 경우가 있다.

 

문제에서 따로 중복에 대한 내용이 없으면 항상 중복 케이스가 있다고 생각하는게 좋다.

 

그렇다면 어떻게 문자열로 된 그래프에서 방문처리를 할까

 

나의 경우 (현재 공항 + 다음 공항의 idx )를 key값으로 사용하여

Set에서 방문처리를 하였다. 

 

이부분만 빼면 딱히 어려운 문제는 아니다. 

 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    static Map<String, List<String>> graph;
    static int n; // 총 방문 도시
    static Set<String> visited = new HashSet<>();
    static String[] answer;
    static boolean isInit = false;
    
    
    public String[] solution(String[][] tickets) {
        n = tickets.length + 1;
        answer = new String[n];
        
        graph = new HashMap<>();
        
        for (String[] ticket : tickets) {
            String start = ticket[0];
            String end = ticket[1];
            
            List<String> list = null;
            if (!graph.containsKey(start)) {
                list = new ArrayList<>();
                list.add(end);
                graph.put(start, list);
                
            } else {
                list = graph.get(start);
                list.add(end);
            }
            
        }
        
        
        String[] path = new String[n];
        path[0] = "ICN";
        
        dfs("ICN", 1, path);
        
        return answer;
    }
    
    private void dfs(String airport, int cnt, String[] path) {
        
        // 경로를 다 만들었으므로 비교 
        if (cnt == n) {
        	// 정답이 아직 없다면 바로 정답으로 초기화
            if (!isInit) {
                isInit = true;
                answer = path.clone();
                
                // path가 앞서는지 검증 
            }else if (!valid(path)) {
                answer = path.clone();
            }
            
            return;
        }
        
        // 마지막 공항이면 탐색 X
        if (!graph.containsKey(airport)) {
            return;
        }
        
        List<String> list = graph.get(airport);
        for (int i = 0; i < list.size(); i++) {
            String check = airport + i;
            
            if (!visited.contains(check)) {
                path[cnt] = list.get(i);
                visited.add(check);
                dfs(list.get(i), cnt + 1, path);
                visited.remove(check);
            }
            
        }
        
    }
    
    // 사전순으로 앞서는지 검증 
    private boolean valid(String[] path) {
       
        for (int i = 0; i < n; i++) {
            int rs = answer[i].compareTo(path[i]);
            
            // path가 사전순으로 더 앞선다면 false
            if (rs > 0) return false;
            
            // answer가 사전순으로 더 앞선다면 true 바로 반환 
            if (rs < 0) return true;
            
        }
        
        return true;
    }
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 비교 결과값에 대해 자주 헷갈리는데 문자도 그냥 숫자로 생각하면 쉽다. 두 파라미터를 1 - 3 으로 생각해서 -면 오름차순 유지, +면 교환이다. 
2.