문제 설명

---

문제

---

문제링크

전체 코드

from collections import defaultdict

def solution(tickets):
    
    def init_graph():
        routes = defaultdict(list)
        for key, value in tickets:
            routes[key].append(value)
        return routes

    def bfs():
        stack = ["ICN"]
        path = []
        while len(stack) > 0:
            top = stack[-1]

            if top not in routes or len(routes[top]) == 0:
                path.append(stack.pop())
            else:
                stack.append(routes[top].pop(0))

        return path[::-1]


    routes = init_graph()
    for r in routes:
        routes[r].sort()

    answer = bfs()
    return answer

---

해결 방법

BFS 문제

먼저 routes에 dict(list)형태로 ticket의 원소를 저장받는다.

routes = defaultdict(list)
for key, value in tickets:
    routes[key].append(value)

그 다음 BFS에서 ICN이 첫번째 도시이므로 stack = ["ICN"], 경로를 받을 path 리스트를 선언하고 stack에 원소가 있을때 stack의 마지막 리스트를 top에 받고 top이 routes의 key에 없거나 routes[top]의 value가 없다면 path에 stack을 pop()하면서 append를 하고 그게 아니라면 stack에 routes[top].pop(0)을 해주면서 append를 한다.