[Python : 프로그래머스] 여행경로

문제

https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3

풀이

재귀 DFS로 풀려하다가, 계속 머리속에서 꼬이는 바람에
그냥 스택으로 풀어냈다. 이게 속편한거 같다 ㅡㅡ;;

• 티켓을 ‘출발지:도착지1,도착지2,…’ 해시테이블로 변환한다.
• 여행경로가 2가지 이상 등장할 경우
  알파벳 오름차순이 기준이므로 출발지별 도착지를 정렬
• 모든 티켓 다 소모할 때까지 스택 DFS 돌리기

def solution(tickets):
    # 해시테이블[출발지] : [도착지1, 도착지2, ...]
    ticket = {}
    for start, end in tickets:
        if start in ticket: ticket[start].append(end)
        else: ticket[start] = [end]
    
    # 알파벳 내림차순 정렬 (pop특성 고려)
    for t in ticket:
        ticket[t].sort(reverse=True)
    
    flying = ["ICN"] # DFS용 스택
    stamp = []      # 이동내역
    while flying:
        top = flying[-1]
        # 스택에서 꺼낸 지역이 마지막 도착지거나, 이미 해당지역 모든 티켓을 소모한 경우
        if not top in ticket or not ticket[top]:
            stamp.append(flying.pop())
        else:   # 그 외엔 해당지역의 앞티켓을 소모해서 스택에 추가한다.
            flying.append(ticket[top].pop())
    
    # 스택 특성 때문에 역순으로 반환
    return stamp[::-1]

재귀/스택 DFS를 몇 차례 짜봤는데 역시 스택이 짜는 과정에서 더 쉽게 이해되긴 한다.
실성능은 재귀가 워낙 뛰어나다보니까 재귀를 연습해야하긴 하는데,
우선 스택으로 싸고 재귀로 변환하는 과정도 시간이 오래걸릴 뿐 나쁘진 않은거같다.
어려우면 이렇게라도 해야지 뭐!

DFS 재귀 풀이

from collections import defaultdict 

def dfs(graph, N, key, footprint):
    if len(footprint) == N + 1:
        return footprint

    for idx, country in enumerate(graph[key]):
        graph[key].pop(idx)

        tmp = footprint[:]
        tmp.append(country)

        ret = dfs(graph, N, country, tmp)

        graph[key].insert(idx, country)

        if ret:
            return ret


def solution(tickets):
    answer = []

    graph = defaultdict(list)

    N = len(tickets)
    for ticket in tickets:
        graph[ticket[0]].append(ticket[1])
        graph[ticket[0]].sort()

    answer = dfs(graph, N, "ICN", ["ICN"])

    return answer

다른 사람 풀이 중 가장 좋아요가 많은 코드.
참고하자.