[프로그래머스] 여행경로 파이썬 풀이

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

프로그래머스

---

1. 풀이

• 일단 딕셔너리 자료 구조에 a 공항에서 방문할 수 있는 모든 도시 정보를 저장하자

프로그래머스 예제 2

 

dfs를 사용하기 위해 딕셔너리 자료 구조가 필요하다. key는 공항이고, value는 해당 공항에서 방문 가능한 모든 도시 정보가 담긴 리스트이다.

이때 각 공항별 방문 가능 도시 정보를 알파벳 역순으로 정렬하자. 나중에 한 도시씩 방문할 때 pop() 메서드를 사용할 것인데, 알파벳 역순으로 정렬되어 있어야 가장 마지막 원소가 알파벳 순으로 가장 앞선 도시이기 때문이다.

 

 

• 방문한 도시를 저장하기 위해 스택 자료 구조를 사용하자

ICN부터 출발하므로, 초기 스택은 ["ICN"]으로 초기화된다. 스택의 가장 마지막 원소가 현재 방문해 있는 공항 정보다.

현재 공항에서 방문할 수 있는 도시들이 있다면, 그곳으로 방문한다는 의미로 stack에 해당 도시를 추가한다. (딕셔너리에서 해당 도시는 제거해준다)

만약 현재 공항에서 더 이상 방문할 도시가 없다면, 해당 공항을 answer에 넣어주고 stack에서 제거한다.

 

 

 

2. 정답 코드

def solution(tickets):
    graph = make_graph(tickets)
    
    stack = ["ICN"]  # ICN으로 시작
    answer = []
    
    while stack:
        top = stack[-1]
        
        if not graph[top]:  # 더 이상 이동할 공항이 없다면
            answer.append(stack.pop())  # 현재 공항 정보(= pop())를 answer에 저장
        else:
            stack.append(graph[top].pop())
            # top 공항과 연결된 공항 중 알파벳 순으로 가장 앞선 것을 pop
            # 해당 공항으로 이동한다.
    
    return answer[::-1]


def make_graph(tickets):
    from collections import defaultdict
    
    graph = defaultdict(list)
    for a, b in tickets:
        graph[a].append(b)
    
    for a in graph:
        graph[a].sort(reverse = True)  # 알파벳 역순으로 정렬
        
    return graph