[코딩테스트 연습] 여행 경로

 

문제: https://programmers.co.kr/learn/courses/30/lessons/43164

---

DFS 문제입니다.

 

DDijkstra님의 풀이를 통해 해결했습니다. (https://devje8.tistory.com/)

 

사전순으로 가장 빠른 경로를 리턴하기 위해 티켓을 '도착지' 기준으로 오름차순 정렬합니다.

 

티켓을 오름차순 정렬 했으므로 ticketList[N]과 ticketList[N+1]의 출발점 공항이 동일하면

ticketList[N]의 도착지 공항이 ticketList[N+1] 도착지 공항보다 알파벳 순서가 앞섭니다.

 

그러므로 for (int index = 0; index < ticketList.size; ++index) 으로 DFS 탐색해도 사전순 탐색이 보장됩니다.

 

주어진 티켓을 전부 사용해야하므로 총 탐색 깊이는 티켓의 갯수입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43164.cc