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

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

프로그래머스

---

배경지식

• 그래프(graphs)란 자료구조
  • 정점(vertex, node)과 간선(edge, link)
  • 유향(directed) 그래프와 무향(undirected) 그래프
• 스택(stack)
• 큐(queue)

깊이 우선 탐색(DFS; Depth First Search)

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

너비 우선 탐색(BFS; Breadth-First Search)

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

문제 풀이

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

 

그래프의 표현

• 사전을 이용하여 각 공항에서 출발하는 항공권의 리스트를 표현한다
  • 이떄 알파벳의 역순으로 정렬해둔다. 리스트를 쓸경우 원소를 앞에서 제거하는것보다 뒤에서 제거하는게 시간복잡도상 유리하므로 역순으로 정렬!
• 인접 행렬: 노드 정보를 2차원 행렬에 기록하는 방식 -> 시간복잡도 $O(N^2)$
  • i에서 j로 가는 경로가 있다면 1, 없다면 0
• 인접 리스트 : 인접 리스트는 그래프의 연결 관계를 vector의 배열로 나타내는 방식입니다. 노드의 개수 V, 에지의 개수를 E라 하면 보통 시간복잡도는 $O(V+E)$
  • 노드 i에 연결된 벡터 정보를 기록하는 방식

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].pop()
    return path[::-1]