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

---

문제 분석

필요 개념

그래프(graphs)

• 정점(vertex, node) 과 간선(edge, link)
• 유향(directed) 그래프와 무향(undirected) 그래프

스택(stack)

큐(queue)

알고리즘

깊이 우선 탐색 (DFS: Deapth-First Search)

• 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
  
• 스택을 이용하여 어느 정점에서 DFS를 하고 있는지를 기억하고 되돌아감

너비 우선 탐색 (BFS: Breadth_First Search)

• 한 정점에서 인접한 모든 (아직 방문하지 않은) 정점을 방문하고, 방붐한 각 인접 정점을 기준으로 (방문한 순서에 따라) 또다시 너비 우선 탐색을 행함
  
• 큐를 이용하여 어느 정점에서 BFS를 해야 하는지를 기록하고 진행함

---

Python 언어를 이용한 풀이

문제의 해결 - DFS

• 한 붓 그리기!
  • 이것이 가능함은 문제에서 보장되어 있음
• 시작 정점은 언제나 "ICN"
• 모든 정점 방문이 아니고, 모든 간선을 거쳐야
  • 언젠가는 한 번 가야 하는데, 그 순서를 결정하라
• 한 정점에서 택할 수 있는 간선이 두 개 이상인 경우?
  • 공항 이름의 알파벳 순서를 따른다.

알고리즘의 설계

• 스택을 이용하여 재귀적인 "한 붓 그리기" 문제를 해결
  • DFS 알고리즘의 응용

요약

• 재귀적인 성질을 가진 "한 붓 그리기" 문제
  • 재귀적인 성질을 가진 "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)
        
    stack = ["ICN"]
    path = []
    
    while len(stack) > 0:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[top][-1])
            routes[top] = routes[top][:-1]
            
    return path[::-1]

시간 복잡도

이렇게 설계한 알고리즘의 복잡도는?

• O(NlogN)

---