[python] 프로그래머스 level3 여행경로 / DFS/BFS

문제

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

프로그래머스

---

접근

1. 출발지를 key, 도착지 배열을 value로 하는 dict 생성

2. 도착지를 내림차순으로 정렬해준다. -> stack.pop()을 사용하면 알파벳 순서대로 확인할 수 있음.

3. 시작지는 ICN이므로 stack에 넣고 시작

• 출발지가 dict에 없거나 (출발할 수 없는 공항, 즉 맨 마지막 도착지가 되는 경우)
• 더이상 이동할 공항이 없거나

  위 두가지 경우, path에 stack.pop()값을 넣어준다.

• 이동할 공항이 있으면 stack에 추가

4. while문이 끝나면 도착지 -> 출발지 순서로된 path 생기므로 뒤집어서 반환해준다.

 

---

코드

from collections import defaultdict, deque

def solution(tickets):
    dic = defaultdict(list)
    
    for a, b in tickets:
        dic[a].append(b)
        
    for key, value in dic.items():
        dic[key].sort(reverse=True)
        
    stack = ['ICN']
    path = []
    while stack:
        dep = stack[-1]
        
        if dep not in dic or not dic[dep]:
            path.append(stack.pop())
        else:
            stack.append(dic[dep].pop())
    return path[::-1]