Programmers_43164 여행경로

function solution(tickets) {
    let answer = ["ICN"];

    // dfs: 경로 탐색
    function dfs(route, ticketCountMap) {
        // 반환 조건: 지나온 공항의 수가 티켓의 수보다 1개 많음
        if (route.length === tickets.length + 1) {
            answer = route;
            return;
        }

        // 새로운 출발지 지정: route의 마지막 원소
        const departure = route[route.length - 1];

        // 해당 출발지의 도착지(arrivalMap)에 대해
        const arrivals = ticketCountMap.get(departure) ?? [];
        arrivals.forEach((ticketCount, arrival, map) => {
            // 아직 티켓을 전부 소진하지 않았으면
            if (ticketCount) {
                // 티켓을 하나 소진하고
                map.set(arrival, map.get(arrival) - 1);
                // route에 해당 목적지를 추가해 dfs를 실행
                dfs([...route, arrival], ticketCountMap);
                // 순회 시에는 영향을 미치면 안되므로 원상복구
                map.set(arrival, map.get(arrival) + 1);
            }
        });
    }

    // 출발지: 해당 출발지에서 도착할 수 있는 도시 배열의 map을 구성
    const ticketMap = new Map([]);
    tickets.forEach(([a, b]) => {
        ticketMap.set(a, [...(ticketMap.get(a) ?? []), b]);
    });

    const ticketCountMap = new Map([]);
    // 각 출발지에 대해
    ticketMap.forEach((value, key) => {
        const arrivalsMap = new Map([]);
        // 도착 공항을 알파벳의 역순으로 순회하면서
        value
            .sort()
            .reverse()
            .forEach((arrival) =>
                // 도착지별 티켓 개수인 arrival map을 구성
                arrivalsMap.set(arrival, (arrivalsMap.get(arrival) ?? 0) + 1)
            );
        // 해당 arrivalMap을 각 출발지에 매핑
        ticketCountMap.set(key, arrivalsMap);
    });

    dfs(answer, ticketCountMap);
    return answer;
}