Developer Wony Story

최단 경로 문제

• 두 노드를 잇는 가장 짧은 경로를 찾는 문제
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 최단 경로 문제
   • 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로 찾는 문제
2. 단일 출발 최단 경로 문제
   • 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
3. 전체 쌍 최단 경로
   • 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제

다익스트라 알고리즘

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제에 적절

다익스트라 알고리즘 로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며 최단 거리를 갱신하는 기법
• 다익스트라 알고리즘은 BFS와 유사
  •  첫 정점부터 각 노드 간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드 간의 가장 짧은 거리를 해당 배열에 업데이트
• 우선순위 큐를 활용 : 우선순위 큐는 Min Heap방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
  1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
     • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장(inf)
     • 우선순위 큐에 (첫 정점, 0)만 먼저 넣음
  2. 우선순위 큐에서 노드를 꺼냄
     • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점만 꺼내짐
     • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교
     • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우 배열에 해당 노드의 거리를 업데이트
     • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다
       -> 결과적으로 너비 우선 탐색과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
       -> 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우에 해당 노드와 인접한 노드 간의 거리 계산을 하지 않음
  3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복

알고리즘 구현

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq

def dijkstra(graph, start):
    distances = { node: float('inf') for node in graph }
    distances[start] = 0
    pq = []
    heapq.heappush(pq, [distances[start], start])
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node]:
            continue
        
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(pq, [distance, adjacent])
                
    return distances

*A부터 F까지의 최단 경로 출력 코드

import heapq

def dijkstra(graph, start, end):
    distances = {node: [float('inf'), start] for node in graph}
    distances[start][0] = 0
    pq = []
    heapq.heappush(pq, [distances[start][0], start])
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node][0]:
            continue
            
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent][0]:
                distances[adjacent] = [distance, current_node]
                heapq.heappush(pq, [distance, adjacent])
    
    path = end
    path_output = [end]
    while distances[path][1] != start:
        path_output.append(distances[path][1])
        path = distances[path][1]
    path_output.append(start)
    path_output = list(reversed(path_output))
    
    return path_output
    
result = dijkstra(graph, 'A', 'F')
print(result)
print("->".join(result))

"""

['A', 'D', 'E', 'F']
A->D->E->F

"""

시간 복잡도

• 과정 1: 각 노드마다 인접한 노드 간선(E)들을 모두 검사 => O(E)
• 과정 2: 우선순위 큐에 노드/거리 정보를 넣고 삭제하는 과정 => O(ElogE)
• 과정 1 + 과정 2의 시간을 합치면 결국 O(ElogE)

BFS와 DFS란?

• 너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색
• 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색
• 시간 복잡도는 정점의 수(V)와 간선의 수(E)를 더한 O(V + E)
• 파이썬에서는 딕셔너리와 리스트 자료구조를 활용해서 구현 가능

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

너비 우선 탐색(BFS)

- 큐의 역할을 하는 visited와 need_visit을 이용해 구현

- 방문한 노드는 visited에, 방문할 노드는 need_visit에 추가

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.appned(node)
            need_visit.extend(graph[node])
    
    return visited

깊이 우선 탐색(DFS)

- 큐의 역할을 하는 visited, 스택의 역할을 하는 need_visit을 이용해 구현

def dfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

탐색할 자료를 두 그룹으로 나누고 찾으려는 데이터가 있을만한 곳을 탐색하는 방법이다.

자세하게 설명하자면 주어진 리스트가 있다고 하자.  여기서 리스트는 반드시 정렬된 상태여야 한다.

우선 리스트의 중간값이 찾으려는 값인지 찾고 찾으려는 값이 중간값보다 작으면 다시 왼쪽으로, 크면 오른쪽으로 좁혀가며 찾아간다. 

1. 분할 정복 알고리즘(Divide & Conquer)

• Divide: 주어진 문제를 작은 단위로 나눈다.
• Conquer: 작게 나누어진 문제를 해결하고 점점 상위 단계의 문제를 해결해 나간다.

이진 탐색도 분할 정복 알고리즘의 형식으로 해결한다. 

2. 코드 구현

def binary_search(data, search):
    if len(data) == 1 and data[0] == search:
        return True
    if len(data) == 1 and data[0] != search:
        return False
    if len(data) == 0:
        return False
    
    mid = len(data) // 2
    if data[mid] == search:
        return True
    elif data[mid] > search:
        return binary_search(data[:mid], search)
    elif data[mid] < search:
        return binary_search(data[mid + 1:], search)