July 01, 2021
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN"
공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets
가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return
하도록 solution
함수를 작성해주세요.
tickets
의 각 행 [a, b]
는 a
공항에서 b
공항으로 가는 항공권이 있다는 의미입니다.return
합니다.처음에는 간단한 문제라고 생각했었다.
모든 항공권을 사용할 수 있다고 해서 ICN > 도칙지
순 으로 정렬을 한 다음, 이어지는 경로의 끝을 찾아야 하므로 dfs
방식으로 해결하려고 했다.
하지만, 1번의 테스트케이스만 계속 시간초과라는 오답을 반환했다.
알아보니, 항공권을 모두 사용할 수 있지만, 중간에 연결이 끊길수 도 있다는 점이였다
결국 정렬은 뒤로하고 모든 항공 경로를 따지기로 하였다. 출발 공항을 강제로 "ICN"
으로 지정해준다면 중요한 정렬자체는 해결되는 셈이였다.
출발지 = "ICN"
, 사용한 항공권
, 누적 경로
를 변수로 받는 재귀함수를 만든다.
visit
과 tickets
의 길이가 동일하다면 누적된 경로를 answers
에 넣고 종료tickets
를 순회하여 해당 함수를 재귀시켜줌
continue
continue
answers
에 담긴 모든 경로들을 한번 정렬해주고, 가장 빠른 0번쨰 경로를 반환한다.
function solution(tickets) {
const answers = []
const dfs = (depart, visit, path) => {
if (visit.length === tickets.length) return answers.push(path)
for (let i in tickets) {
if (tickets[i][0] !== depart) continue
if (visit.includes(tickets[i])) continue
dfs(tickets[i][1], [...visit, tickets[i]], [...path, tickets[i][1]])
}
}
dfs('ICN', [], ['ICN'])
// 배열 내에서 값들을 빠른순으로 정렬
return answers.sort()[0]
}
bfs
, dfs
자료구조를 해결하는데에는 재귀가 단순하면서도 최고인듯 하다.sort
는 생각보다 친절했다.