프로그래머스 여행경로 JavaScript
2023년 2월 14일
문제 풀이
주어진 항공권을 모두 이용하여 여행경로를 짜 공항 경로를 배열로 담아 리턴하는 문제, 조건은
- 항상 "ICN" 공항에서 출발
- 주어진 항공권을 모두 사용
- 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경우를 리턴
- 모든 도시를 방문할 수 없는 경우는 없음
- 모든 공항은 알파벳 대문자 3글자
우선 모든 항공권을 이용했음을 체크하기 위해 배열 check를 항공권 길이만큼 0으로 채운다.
모든 항공권을 이용했을 때는 route의 길이가 check.length+1일 때다. 그 외에는 현재 사용 가능한 항공권인지 확인하고 가능하면 재귀 호출한다.
(function dfs(v, route): v는 현재 도시, route는 현재 이동한 경로)
항상 "ICN" 공항에서 출발하기에 dfs("ICN", ["ICN"])로 dfs를 시작하고 가능한 경로가 2개 이상일 경우를 대비해 sort()한 뒤 첫 번째 경로를 리턴한다.
solution.js
function solution(tickets) {
const routes = [];
const check = new Array(tickets.length).fill(0);
const dfs = ((v, route) => {
if (route.length === check.length + 1) {
routes.push(route);
return;
}
tickets.forEach((ticket, index) => {
if (ticket[0] === v && check[index] === 0) {
check[index] = 1;
dfs(ticket[1], [...route, ticket[1]]);
check[index] = 0;
}
});
});
dfs("ICN", ["ICN"]);
return routes.sort()[0];
}