[프로그래머스] 여행경로 C++

 

코딩테스트 연습 - 여행경로

 

 

문제풀이

 

주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다.

항상 "ICN" 공항에서 출발한다.

가능한 경로가 2개 이상일 경우에는 알파벳 순서가 앞서는 경로를 리턴한다.

주어진 항공권은 모두 사용해야 한다.

 

 

이 문제에서 주의해야 할 점은 주어진 항공권을 모두 써야한다는 것이다.

알파벳 순서가 앞서는 경로를 선택해서 갔을 때 항공권을 모두 사용하지 못하는 경우가 있다.

 

 

테케 하나를 예로 살펴보자.

 

[["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"],

["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]

 

"ICN" → "BOO" → "DOO" → "BOO" → "ICN"→"COO"까지는 알파벳 순서가 앞서는 경로를 따라간다면 쉽게 구할 수 있을 것이다.

 

이때 남아있는 티켓은 ["COO", "BOO"], ["COO", "DOO"], ["DOO", "COO"] 3개다.

알파벳 순서가 앞서는 경로를 따른다면 다음 공항은 "BOO"여야 한다.

 

하지만 "BOO" 공항으로 가면 남은 ["COO", "DOO"], ["DOO", "COO"] 티켓을 쓰지 못한다.

"BOO" 공항에서 "COO" 공항이나 "DOO" 공항으로 갈 수 없기 때문이다.

그래서 이때는 알파벳 순서가 앞서는 "BOO"보다 "DOO" 공항으로 가야 남은 티켓을 모두 쓸 수 있다.

 

 

 

모든 티켓을 쓰는 경로를 찾기 위해서 dfs를 bool 타입으로 선언해주었고 모든 티켓을 다 쓴 경우, 즉 cnt == n인 경우에 탐색을 종료하도록 코드를 짰다.

 

다음에 방문할 공항을 찾기 위해 tickets[i][0]이 현재 있는 공항인 티켓을 찾아서 모두 next 벡터에 저장해둔다.

알파벳 순서대로 정렬한 후에 각 티켓을 써보고 모든 티켓을 다 쓴 경로를 찾을 경우 종료해준다.

 

 

C++ 코드