[Python] 프로그래머스 - 여행경로 (DFS/BFS)

문제 설명

📃 문제 링크

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

tickets	return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

문제 풀이

dict 타입인 routes에 출발지와 도착지를 key, value로 묶어준다. 만약 "ICN"에서 갈 수 있는 곳이 "SFO"와 "ATL" 두 곳이 있다면 "ICN" : ["SFO", "ATL"] 이런 식으로 들어갈 수 있도록 만들어준다.

알파벳 순서가 앞서는 경로를 먼저 선택해야 하고, value에서 하나씩 꺼내서 맞는 경로인지 판별해줄 것인데 value를 스택으로 사용할 것이기 때문에 사전 순으로 앞선 도착지를 먼저 꺼낼 수 있도록 내림차순으로 정렬해준다.

현재 출발지는 current_list에 넣어 주고, 가장 최근에 추가된 출발지 = 현재 출발지(current)에서 갈 수 있는 도착지가 존재할 경우 갈 수 있는 도착지들 중 알파벳이 앞선 도착지를 꺼내 current_list에 넣어 준다.

도착지가 존재하지 않을 경우에는 answer에 현재 출발지를 pop해서 넣어 준다. current_list에 저장된 경로가 올바른 경로일 경우 쭉 answer에 저장될텐데, 끝에서부터 저장되었기 때문에 다시 역순으로 바꾸어 리턴해준다.

소스 코드