문제 접근

티켓들이 주어진다. 각 티켓은 시작 지점과 도착지점에 대한 정보가 있다.
우리의 여행 출발 도시는 "ICN" 이다.
ICN 부터 시작해서 사전 글자 순서대로 방문해야한다.

한 번 지난 도시를 다시 지날 수 있으며, 모든 티켓을 소모해야한다.

즉, 이 문제는 인접리스트를 사전 순으로 정렬하고, 만약 티켓이 다 소모가 안됐는데 더이상 해당 도시에서 이동할 수 있는 티켓이 남아있지 않다면 실패한 것으로 취급하고 다시 뒤로 되돌리는 방식의 dfs를 활용할 수 있다. 물론 bfs로도 잘 구현하면 되겠지만, 여행경로를 저장해야 한다는 특성 때문에 여기서 저는 dfs 구현이 더 쉬워보여서 dfs를 선택했습니다.

문제 풀이

import java.util.*;

class Solution {
    String[] answer;
    HashMap<String,ArrayList<Ticket>> maps = new HashMap();
    int ticketsSize;
    public String[] solution(String[][] tickets) {
        ticketsSize = tickets.length;
        answer = new String[tickets.length + 1];
        answer[0] = "ICN";
        for(int i=0; i<tickets.length; i++) {
            ArrayList<Ticket> arrays = maps.getOrDefault(tickets[i][0], new ArrayList());
            arrays.add(new Ticket(tickets[i][1]));
            maps.put(tickets[i][0], arrays);
        }
        for(String s: maps.keySet()) {
            ArrayList<Ticket> arrays = maps.getOrDefault(s, new ArrayList());
            Collections.sort(arrays, (t1, t2)->{
               return t1.e.compareTo(t2.e); 
            });
        }
        
        dfs("ICN", tickets.length);
        return answer;
    }
    
    boolean dfs(String curNode, int remainTickets) {
        if (remainTickets == 0) { 
            return true;
        }
        
        ArrayList<Ticket> arrays = maps.getOrDefault(curNode, new ArrayList());
        
        for(Ticket neigh: arrays) {
            if (neigh.v) continue;
            neigh.v = true;
            answer[ticketsSize - remainTickets + 1] = neigh.e;
            
            boolean result = dfs(neigh.e, remainTickets-1);
            if (result) return true;
            
            answer[ticketsSize - remainTickets + 1] = "";
            neigh.v = false;
        }
        return false;
        
        
    }
}

class Ticket {
    String e;
    boolean v = false;
    Ticket (String e) {
        this.e = e;
    }
}

자주 안쓰면 잊어먹는 복습할 거리들

1. HashMap의 getOrDefault와 put함수
   • getOrDefault로 생성한 기본 값을 put으로 할당하지 않는다면 저장되지 않는다.
2. HashMap의 ketSet()과 values()
   • 참고로, keySet()은 Set을 반환하고,
   • values()는 Collections를 반환해서 오직 for(:~.values()) 형식으로만 가능하다.
3. 문자열 정렬은 String1.compareTo(String2) 의 반환타입을 쓰면 된다.
   • 두 값이 같다면 0
   • 첫번째 인자가 사전 순서상 더 작다면(먼저 앞에 온다면) 음수
   • 두번째 인자가 사전 순서상 더 작다면 양수임. -> 양수라는 것은 둘을 바꿔야 사전 오름차순이 될 수 있다는 것을 내포하고 있기도 하다.