Step 7: 깊이/너비 우선 탐색(DFS/BFS) 대표 문제 풀이: 여행경로

강의

"깊이 우선 탐색"은 한 정점에서 인접하고 아직 방문하지 않은 모든 정점을 방문할 때, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝내고 다음 정점으로 이동하는 알고리즘 입니다.

"너비 우선 탐색"은 한 정점에서 인접하고 아직 방문하지 않은 모든 정점을 방문할 때, 방문한 각 인접 정점을 기준으로 방문한 순서에 따라 너비 우선 탐색을 행하는 알고리즘 입니다.

 

 

Step 7-3: 풀어서 내 것으로 만들자! 여행 경로

⭐ 힌트 풀이 : stack과 DFS를 이용하여 푸는 문제!

def solution(tickets):   
    routes = {}
    
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    
    for r in routes:
        routes[r].sort(reverse = True)
        
    visited = ["ICN"]
    
    path = []
    
    while len(visited) > 0:
        top = visited[-1]
        
        if top not in routes or len(routes[top]) == 0:
            path.append(visited.pop())
        
        else:
            visited.append(routes[top][-1])
            routes[top] = routes[top][:-1]
        
    return path[::-1]