[Level 3] 여행 경로

programmers.co.kr/learn/courses/30/lessons/43164

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

---

접근

DFS로 ICN을 출발하여 깊게 탐색해 나간다. 탐색하다가 더이상 방문할 공항이 없을 때 경로에 하나씩 추가해온다.

DFS를 재귀로 구현을 하면 도착점에서부터 경로에 추가되어 오기 때문에 마지막에 뒤집어서 반환하도록 한다.

 

구현

defaultdict는 딕셔너리를 생성하는 것인데 인자로 주어진 값으로 초기화를 한다. 여기서 리스트로 초기화되었기 때문에 해당되는 key에 value를 추가할 수 있었다.

또한 알파벳 순으로 방문하기 때문에 내림차순으로 정렬하여 맨 뒤에 가장 빠른 알파벳을 가진 공항이 오도록 하였다. 왜냐하면 pop을 하면 맨 뒤의 원소가 먼저 나오기 때문이다.

from _collections import defaultdict
def solution(tickets):
    answer = []
    graph = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)

 

ICN 공항부터 DFS를 시작한다. 현재 시작점에 포함된 도착지들을 DFS에 넣어 재귀호출을 한다. 끝에 가서는 해당 시작점에서 출발할 공항이 없어지기 때문에 최종 도착점에서부터 answer에 추가해서 재귀를 빠져나오게 된다.

def dfs(start):
    while graph[start]:
       dfs(graph[start].pop())
    answer.append(start)

 

그렇기 때문에 최종적으로는 뒤집어서 ICN에서 최종 도착지 순으로 리스트에 담기로고 한다.

answer = answer[::-1]

---

전체 코드

from _collections import defaultdict
def solution(tickets):
    answer = []
    graph = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)
    
    def dfs(start):
        while graph[start]:
            dfs(graph[start].pop())
        answer.append(start)
    dfs('ICN')
    answer = answer[::-1]
    return answer