[프로그래머스💯] 코딩테스트 연습 > (DFS/BFS) > 여행경로 / Python 문제풀이

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

from collections import defaultdict


def solution(tickets):

    START = "ICN"
    citiesDests = defaultdict(list)

    for ticket in tickets:  # 한도시당 edge 수를 계산
        citiesDests[ticket[0]].append(ticket[1])
    for city in citiesDests.keys():
        citiesDests[city].sort()
    # print(citiesDests)
    stack = []
    res = []

    def Go(start):
        stack = []
        stack.append(start)
        if len(citiesDests[start]) == 0:
            # print("현재 stack => ", stack)
            # print("here, start=>", start)
            top = stack.pop()
            # print("변화 stack => ", stack)
            # print("append top => ", top)
            res.append(top)
            return
        for city in citiesDests[start][:]:
            if city not in citiesDests[start]:
                continue
            citiesDests[start].remove(city)
            Go(city)
        while stack:
            res.append(stack.pop())

    Go(START)
    res.reverse()

    return res

 

 

풀이)

Stack 을 이용한 DFS 풀이 입니다.

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges