23.03.09 파이썬 코딩 퀴즈#190 여행경로(프로그래머스 스쿨)

이번 문제는 여행경로 문제이다.

tickets 에는 시작공항,출발공항 이 좌표형태로 전달되며, 해당 티켓을 모두 사용하여 방문하는 공항 경로를 배열에 담아 return 해야 한다.

만약 가능한 경로가 2개 이상이라면, 알파벳 순서가 앞서는 경로를 return 해야 한다.

입출력 예 2번에서 알수 있듯이 ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순서로도 방문 가능하지만, "ICN"을 기준으로 "ATL" 이 우선이기 때문에 ICN -> ATL -> ICN 이 우선이 되고 그 다음 ICN -> SFO -> ATL -> SFO 순서이다.

시작 공항은 항상 ICN 이다.

 

한가지 중요한점은 위 예시에서도 설명이 되었지만 순항편이 존재하는 경우이다.

항상 "ICN"을 기준으로 순항편이 존재하면 문제 없겠지만, 중간에 다른 공항에 순항편이 존재하면 그 순항편을 먼저 여행하고 다른 공항으로 넘어가야 한다. 코드를 구현하면서 이 부분이 제일 까다로웠다.

먼저 solution() 함수를 보자.

시작 공항은 언제나 'ICN' 이기에 answer에 넣어주고 시작한다.

남은 티켓을 확인하기 위해 remained_tickets 배열을 사용하였다.

이제 본격적으로 dfs() 함수를 확인해보자.

먼저 tickets 이 없는 경우라면 진행이 불가능하기 때문에 그냥 return 으로 종료를 선언해 주었다.

temp 는 dict 이든 list 이든 상관이 없다.

이제 반복문으로 tickets 를 탐색하여, 현재 공항에서 이동 가능한 표가 있는지 확인하고, 표가 남아있다면 해당 표의 목적지와 티켓 번호(i)를 temp 에 저장한다.

이제부터가 굉장히 중요한데, 먼저 이동 가능한 표가 있는 경우부터 살펴보자.

예를 들어 tickets = [["ICN", "A"], ["A", "B"], ["A", "C"], ["C", "A"], ["B", "D"],["A", "D"]] 라고 가정하면,

위 그림과 같이 여행이 가능하다.

하지만 ICN 에서 A 로 이동한 다음 문제가 발생한다.

알파벳 순서로 정렬했기 때문에 B 공항을 탐색하고, D 공항을 탐색한다.

하지만 아직 티켓이 남았고, 이동 가능한 공항이 없기 때문에 answer 에서 'D'를 remained_tickets 으로 넘긴 후 B를 기점으로 탐색하고, B에서도 이동 가능한 티켓이 없기 때문에 다시 A로 올라가게 된다.

그리고  이제 C 로 이동하는 왕복티켓을 사용하고 dfs() 함수는 종료된다.

따라서 answer 에는 [ICN, A, C, A] 가 담겨있다.

remained_tickets 에는 ['D', 'B'] 가 남아있다. pop()을 이용해 제일 최근에 추가된 도시부터 answer에 전달하면 완성이다.

 

여기서 한가지 의문이 생겼다.

만약 B 에서 새로운 도시 E 로 가는 왕복티켓을 추가하게 된다면 어떻게 작동할까?

똑같은 방법으로 dfs() 함수는 작동하게 되고, remained_tickets 에는 [D,B,E,B] 순서로 저장이 된다. 

순서대로 마지막 추가값부터 answer에 붙이면 완성이다.

 

즉 remained_ticket에는 우선 방문한 도시의 순항편을 돌고 난 다음 방문해야할 도시들이 역순으로 전달되는걸 확인 할 수 있다.

 

문제 설명이 다소 아쉬운 문제였다.

모든 공항을 다 방문가능하다는 설명과 알파벳순 정렬의 의미를 테케를 통해서 좀 더 직관적으로 보여줬다면 좋았을 것 같다.