출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43164
[문제 설명]
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
[제한사항]
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
[입출력 예]
[입출력 예 설명]
[예제 #1]["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.
[예제 #2]["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.
[코드]
function solution(tickets) {
let result = [];
// (잔여 티켓, 현재 위치, 여행 경로)
function DFS(tickets, current, route){
if (!tickets.length) { // 티켓 모두 사용
result.push(route);
}
else {
tickets.forEach(([departure, arrival], index) => {
if (current === departure) {
const remain = tickets.slice(); // 남은 티켓
remain.splice(index, 1); // 사용 티켓 제거
DFS(remain, arrival, route.concat(arrival)); // 경로에 추가
}
});
}
};
DFS(tickets, 'ICN', ['ICN']); // 출발지 ICN 세팅
return result.sort()[0]; // 알파벳 순 정렬
}
Cho