# 여행 경로

## **문제 설명**

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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` 변수가 정의되고 반환될 수 있었다.

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

```javascript
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]

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

### 다른 풀이

그래서 다른 코드들을 보고 문제점을 파악할 수 있었다. [참고](https://grahams.tistory.com/388)

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

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

```javascript
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];
}
```