깊이/너비 우선 탐색(DFS/BFS)-여행경로*

def solution(tickets):

    routes = dict()

    for t1, t2 in tickets:
        if t1 in routes:
            routes[t1].append(t2)
        else:
            routes[t1] = [t2]
    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    st = ['ICN']
    ans = []
    while st:
        top = st[-1]
        if top not in routes or len(routes[top])==0:
            ans.append(st.pop())
            
        else:
            st.append(routes[top].pop())

    ans.reverse()
    return ans

... 아직 dfs-bfs 가 익숙하지 않다.  엄청 어렵다. 

 

step 1 ) 갈 수 있는 경로를 정의 한 routes 딕셔너리를 만든다. 

step 2 ) 문제에서 가능한 알파벳 순으로 나열하라고 했으므로 정렬한다. 이 때, 역으로 정렬하여 pop 했을 때 

           알파벳 순서가 빠른 곳이 먼저 나오도록 한다. 

step 3 ) 시작점은 'ICN' 이다. 

step 4 ) 문제에서 무조건 다 사용할 수 있다고 했으므로, 다음과 같은 알고리즘을 적용할 수 있다. 

           만약 내가 가려는 곳이 routes 에 존재하지 않는다면 ans 에 넣는다. 마지막에 다른 곳에서 이곳에 도착할 

           것이 분명하다.  존재한다면 다음 목적지로 삼으면 된다. 

 

 

Reference 

 

아래 블로그를 참고했음. 설명이 잘 되어있다. 

 

https://gurumee92.tistory.com/165

프로그래머스 문제 풀이 여행 경로