[프로그래머스 Level 3] 여행경로 - JavaScript

🔗 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

✏️ 풀이

function solution(tickets) {
    const graph = {};
    const count = {};
    tickets.forEach(([from, to]) => {
        if (graph[from]) {
            graph[from].push(to);
        } else {
            graph[from] = [to];
        }
        const ticket = from + to;
        if (count[ticket]) {
            count[ticket]++;
        } else {
            count[ticket] = 1;
        }
    });
    
    Object.keys(graph).forEach(key => graph[key].sort());
    
    let output;
    let flag = true;
    const dfs = (from, ticketCount, route) => {
        if (ticketCount === 0) {
            output = [...route];
            flag = false;
            return;
        }
        if (!graph[from] || !flag) {
            return;
        }
        graph[from].forEach(to => {
            const ticket = from + to;
            if (count[ticket]) {
                count[ticket]--;
                ticketCount--;
                route.push(to);
                dfs(to, ticketCount, route);
                count[ticket]++;
                ticketCount++;
                route.pop();
            }
        });
    };
    
    dfs('ICN', tickets.length, ['ICN']);
    
    return output;
}

주어진 항공권 정보를 통해 인접 배열(graph)을 만든다. 이 때, 항공권의 사용 여부를 기록하기 위해 count 객체에 공항경로별로 항공권이 몇 장이 있는지도 따로 기록하였다. ("출발공항" + "도착공항" 6자리 문자열로 기록하였다)

 

가능한 경로가 여러 개 있을 경우 이름 순으로 더 앞서는 경로를 찾아야 하므로, 인접 배열을 전부 오름차순으로 정렬해서 나중에 DFS를 할 때 이름 순서가 더 빠른 공항부터 탐색하도록 하였다.

 

DFS를 하면서 남은 항공권 개수가 0개가 되면 모든 항공권을 사용한 것이므로 output을 현재까지의 경로로 갱신한다. 아직 남은 탐색을 탈출할 방법이 없기 때문에 flag 변수를 갱신해서 재귀를 탈출할 수 있도록 하였다.이 외에도 현재 공항에서 이동할 수 있는 공항이 없으면(인접 배열이 비어 있으면) 함수를 종료한다.

 

현재 공항에서 이동할 수 있는 공항이 있다면, 아까 전에 정렬된 순서(알파벳 오름차순)로 공항을 순회한다.

만약 현재 공항에서 그 다음 공항으로 가는 항공권이 남아있다면(count[ticket]) DFS를 재귀호출하여 해당 경로로 탐색을 진행한다. DFS 탐색이 끝나면 현재 경로에 해당하는 항공권의 개수, 전체 항공권 개수, 지금까지의 경로(route)를 다시 원상복구한다.

 

위 과정을 통해 전체 경로를 모두 탐색하고 첫 번째로 발견된 경로를 output에 저장하여 반환하게 된다.

 

 

⛔ 반례

입력: [["ICN", "A"], ["ICN", "B"], ["B", "ICN"]]
출력: ["ICN", "B", "ICN", "A"]

알파벳 순서상 ICN -> A로 가야 하지만, A로 가면 B를 방문할 수 없다.