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

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

코딩테스트 연습 - 여행경로 | 프로그래머스

Copy-Driven-dev 닉값했다.

개인적으로는 재귀를 정말 싫어하는데, DFS는 재귀를 많이 쓰더라. 

대충 방식은 재귀를 쓰나 안쓰나 같다.

 

1. 티켓을 출발-도착 순으로 나눠서 dict에 넣는다.
2. 티켓의 도착지를 역순으로 저장한다.
3. 스택을 만들고 돌면서
   1. 티켓의 출발지에 없거나 -> top not in t 있어도 도착지를 다 돌았으면 -> len(t[top])==0
      1. 스택의 맨 위를 답에 넣는다.
      2. 더이상 들어갈데가 없다.
   2. 아니면 -> 아직 갈데가 있다 -> 탐색 거리가 있다.
      1. 스택에 t[top]의 맨 위를 넣는다.
4. 스택이면 거꾸로 들어가므로 -> 답을 뒤집는다.

 

def solution(tickets):
    t = dict()
    for ticket in tickets:
        if ticket[0] in t:
            t[ticket[0]].append(ticket[1])
        else:
            t[ticket[0]] = [ticket[1]]


    for k in t.keys():
        t[k].sort(reverse=True)
            

    st = ["ICN"]
    answer = []

    while st:
        top = st[-1]


        if top not in t or len(t[top]) ==0:
            answer.append(st.pop())

        else:
            st.append(t[top][-1])
            t[top].pop()

    answer.reverse()
        
    return answer