프로그래머스 데브코스 - [3단계] 여행경로

 

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

 

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

 

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

 

풀이

주어진 문제에서 핵심 포인트는 모든 경로를 지나야 한다는 것이다. 그렇다면 BFS와 DFS를 고민하게 되는데 이 문제의 경우에는 최단경로를 구하는것이 아니므로 DFS를 사용한다

우선 경로를 인접리스트로 표현하기 위해 그래프를 구성한다

DFS에서 경로를 스택에 push 하고 pop하기위해 그래프의 key값을 역순으로 정렬한다

DFS를 사용해 스택에 더이상 경로가 없을 때 까지 인접리스트를 방문한다

function solution(tickets) {
    // 경로를 인접 리스트로 그래프를 구성
    const ticketGraph = {};
    for (const [src, dest] of tickets) {
        if(ticketGraph[src] === undefined) {
            ticketGraph[src] = [];
        }
        ticketGraph[src].push(dest);
    }
    
    // 그래프의 key값을 기준삼아 역순으로 정렬
    for (const key in ticketGraph) {
        ticketGraph[key].sort((a, b) => a > b ? -1 : 1);
    }
    
    // DFS를 위한 스택, "ICN"공항에서 시작
    const stack = ["ICN"];
    const answer = [];
    
    // DFS
    while (stack.length > 0) {
        // stack의 마지막요소를 출발지로 설정
        const src = stack.at(-1);
        // 인접 리스트에서 출발지로부터 도착지가 존재한다면
        if(ticketGraph[src] && ticketGraph[src].length > 0) {
            // 도착지를 인접리스트에서 pop한 후 스택에 push
            stack.push(ticketGraph[src].pop());
        // 인접 리스트에서 출발지로부터 도착지가 없다면
        } else {
            // 스택에서 pop한 후 answer 배열에 push
            answer.push(stack.pop());
        }
    }
    
    // answer 배열에 경로의 역순으로 push 되었기 때문에 뒤집어서 리턴
    return answer.reverse();
}

 

후기

지난 가장 먼 노드 문제와 이번 문제를 통해서 경로를 방문하고 최단거리를 구하는 문제에서는 BFS, 그게 아니라면 DFS를 사용하는 것이 문제 해결하는데 수월하다는 것을 깨닫게 되었다