[프로그래머스] 깊이/너비 우선 탐색 - 여행경로 문제 풀이 (feat.JS)

오늘은 오랜만에 프로그래머스에서 코딩테스트 고득점 Kit의 문제를 풀어보겠습니다. 깊이/너비 우선 탐색 문제 중 여행경로 문제 풀이를 해보겠습니다. 오랜만에 코딩테스트 고득점 Kit 문제로 돌아온 만큼 깔끔하게 문제를 풀어보겠습니다.

 

 

프로그래머스 > 깊이/너비 우선 탐색(DFS/BFS) > 여행경로 문제 풀이

 

 

 

 

◐ 문제 정보

• 문제명: 여행경로
• 문제 난이도: Level 3
• 문제 푼 사람 수: 12298명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

◐ 문제 설명

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

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

 

 

여행경로 문제는 정말 짧습니다. 하지만 여행경로 문제 풀이를 위하여 이해하기 쉽도록 문제 내용을 정리해보겠습니다.

• 주어진 항공권을 모두 이용하여 여행경로를 구하기
• Input
  • tickets: 항공권 정보가 담긴 2차원 배열
• Output: 항공권 정보로 순서대로 방문하는 공항 경로

 

 

 

 

◐ 제한 사항

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

 

 

• 공항 이름은 알파벳 대문자 3글자
• 3 ≤ 공항 수(N) ≤ 10,000
• tickets의 각 요소는 [A, B]의 형태이며, A 공항에서 B공항으로 가는 항공권이 있음을 의미
• 주어진 항공권은 모두 사용해야 한다.
• 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로
• 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

 

 

 

 

◐ 입출력 예

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"] 가 알파벳 순으로 앞섭니다.

 

 

 

 

◐ 알고리즘 만들기

1. 모든 항공권에 대해서 출발 공항을 Key로, 도착 공항을 Value로 갖는 Map을 만든다.
2. Map을 기반으로 깊이 우선 탐색(DFS)을 통해 경로들을 문자열로 구한다.
   2-1. 시작 공항은 ICN으로 한다.
   2-2. 경로 문자열은 구분자(',(쉼표)',' (띄어쓰기)' 와 같은)를 통해 공항명을 구분한다.
3. 구해진 경로를 알파벳으로 정렬하여 가장 앞의 경로를 배열로 변환하여 반환한다.

 

 

위의 여행경로 문제 풀이 알고리즘에서 주요한 부분은 경로를 문자열로 만든 것입니다.

이 부분은 제한 사항에서 여러 경로를 찾았을 경우, 알파벳 순으로 앞선 경로를 찾아야 하기에, 정렬하기 편한 하나의 문자열로 만들었습니다. 또한, split() 함수를 통해 결과로 반환해야하는 형태인 배열로 만들기 쉽도록 구분자를 두어 경로 문자열을 만들었습니다.

 

 

그럼 위 알고리즘을 토대로 여행경로 문제 풀이를 JavaScript로 구현해보도록 하겠습니다.

 

 

 

 

◐ 코드 구현

function solution(tickets) {
    var paths = [];
    // 1. 모든 항공권에 대해서 출발 공항을 Key로, 도착 공항을 Value로 갖는 Map을 만든다.
    const ticketPath = tickets.reduce((prev, ticket) => {
        prev.set(ticket[0], prev.get(ticket[0]) ? [...prev.get(ticket[0]), ticket[1]] : [ticket[1]]);
        return prev;
    }, new Map());

    // 2. Map을 기반으로 깊이 우선 탐색(DFS)을 통해 경로들을 문자열로 구한다.
    //    2-1. 시작 공항은 ICN으로 한다.
    getTravelPath(ticketPath, 'ICN');

    function getTravelPath(pathMap, path, count = 1) {
        const curAirport = path.substring(path.length-3);

        if(count === tickets.length + 1) {
            paths.push(path);
            return;
        }

        for(let i = 0; i < (pathMap.get(curAirport) || []).length; i++) {
            const curPath = pathMap.get(curAirport);
            const airport = curPath.shift();
            // 2-2. 경로 문자열은 구분자(',(쉼표)',' (띄어쓰기)' 와 같은)를 통해 공항명을 구분한다.
            getTravelPath(pathMap, path + ',' + airport, count + 1 );
            curPath.push(airport);
            pathMap.set(curAirport, curPath);
        }
    }

    // 3. 구해진 경로를 알파벳으로 정렬하여 가장 앞의 경로를 배열로 변환하여 반환한다.
    paths.sort();

    return paths[0].split(',');
}

 

 

 

 

◐ 채점 결과

 

 

JavaScript로 구현한 여행경로 문제 풀이 채점 결과 정확성 테스트 케이스 4개를 모두 통과하여 완료하였습니다.