🤔여행 경로

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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"] 가 알파벳 순으로 앞섭니다.

코드

코드 작성 중 while문을 while(queue) 로 작성했었는데, 이 경우 answer이 undefined로 나타났다.

❓이유는 while 루프가 queue 배열이 비어있지 않은 경우에만 실행충족이 되는데, queue 배열이 비어 있으면 while 루프는 실행되지 않고 즉시 종료된다. 이 경우 answer 변수가 정의되지 않고 undefined 값이 유지된다.

👉 해결한 방법: while 루프 조건을 queue.length > 0 으로 변경하여 해결하였다. 이렇게 하면 queue 배열이 비어 있어도 while 루프가 한 번 더 실행되어야 하므로 answer 변수가 정의되고 반환될 수 있었다.

다르게 해결하는 방법이 있다면 좀 더 고민해봐야 할 것 같다.

function solution(tickets) {
    // 시작할 노드 지정 'ICN'으로 시작하면서 알파벳 순서가 앞서는 경로
    const start = tickets.filter(v => v[0] === 'ICN').sort()[0]
    const index = tickets.indexOf(start);
    
    let answer = ['ICN'];
    let queue = [[start, index]];
    
    while(queue.length > 0) {
        if(tickets.length == 0) return;
        let [node, curIdx] = queue.shift();
        answer.push(node[1]);
        tickets.splice(curIdx, 1);
        let next = tickets.filter(v => node[1] === v[0]).sort()[0];
        next && queue.push([next, tickets.indexOf(next)]);
    }
    return answer;
}

이렇게 코드를 짠 후에 처음으로 주어지는 테스트 케이스는 통과를 했는데, 제출 후의 4개의 테스트 케이스 중 1, 2번의 테스트 케이스에서 실패가 떴다.🥲

1. 문제에서 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 하도록 되어 있는데, 내가 작성한 코드에서는 알파벳순으로 앞서는 경로를 선택하는 조건 때문에 경로를 구성할 수 없는 경우가 발생할 수 있다. 그래서 경로가 실패한 경우에 다시 경로 선택 전으로 되돌아가서 코드를 짜야한다.

🚨 tickets 예시

[["ICN", "JFK"], ["ICN", "AAD"], ["JFK", "ICN"]]

→ [ICN, JFK, ICN, AAD]

1. 문제에서는 동일한 표가 중복될 수 없다는 조건이 존재하지 않는다. 때문에 티켓을 지우면서 내려갈 때 ICN → JFK, ICN → JFK 이렇게 두장 있을 수 있는 경우가 있으므로 이 부분을 고려해서 작성하자.

다른 풀이

그래서 다른 코드들을 보고 문제점을 파악할 수 있었다. 참고

정렬을 기준으로 출발지를 정하는 것이 아니라, 일단 가능한 경로를 모두 탐색한 후에 sort()로 정렬해서 가져오면 됐다!

이 코드는 DFS를 이용해서 풀었는데 훨씬 깔끔하다.

function solution(tickets) {
    let answer = [];
    
    function DFS(cur, extra, path) {
        if(extra.length === 0) {
            answer.push(path);
            return;
        }
        extra.forEach(([start, end], idx) => {
            if(cur === start) {
                const newExtra = extra.slice();
                newExtra.splice(idx, 1); // 사용한 티켓 삭제
                // 남은 잔여티켓, 새 목적지 입력해서 재호출
                DFS(end, newExtra, [...path, end]);
            }
        })
    }
    // 초기값 설정
    DFS('ICN', tickets, ['ICN']);
    
    
    return answer.sort()[0];
}