[CS 개념 정리] 이분 탐색, 최단 경로(다익스트라), 최소 비용(MST)(크루스칼, 프림) - 파이썬 코드 구현

이분탐색이란?

: 이진탐색이란 '정렬된 자료'를 반으로 쪼개가며 원하는 값을 찾아가는 탐색 알고리즘

* 가운데 지점(mid)을 찾고, 계속 left, right 값을 mid를 이용해 갱신하면서 범위를 좁혀나가는 알고리즘

위 - 이분탐색, 아래 - 순차 탐색

• 최선: O(1)
• 평균: O(log N)
• 최악: O(log N) >> 데이터가 한 개 남을 때 까지 찾는 경우가 최악

# 이분탐색 알고리즘 (정방향)
def BinarySearch(arr,target):
    #L: left, R: Right, M: Mid
    L,R = 0, len(arr)-1
    while(L <= R): # L>R 되면 탈출 (배열에 target이 없다)
        M = (L + R) // 2
        if(arr[M] == target): # target값에 해당하는 idx 찾음
            return M
        elif(arr[M] > target): # target 값보다 더 클 때
            R = M - 1 # R을 중간-1 의 idx로 갱신 
        else: #target 값보다 더 작을 때
            L = M + 1 # L을 중간+1 의 idx로 갱신
    return -1 #배열 내에 값이 없음

---

최단 경로(다익스트라)란?

: 다이나믹 프로그래밍을 활용해 최단거리를 찾는 알고리즘. 특정 source 노드에서 다른 점으로 가는 최단 경로를 알려줌

 

다익스트라가 다이나믹 프로그래밍인 이유:

이전에 구했던 최단거리를 이용해서 다음 최단거리를 계산하기 때문 (DP 조건은 부분 문제 반복과 최적 부분 구조)

 

>> 다이나믹 프로그래밍 정리 글

[알고리즘 개념 정리] 분할 정복법 (Divide and Conquer), 탐욕 알고리즘 (Greedy), 동적 계획법 (Dynamic Prog

 

최단 경로 코드 구현 - 파이썬

• 출발 노드와, 도착 노드를 설정 (전체 거리를 알고 싶을 때는 출발 노드만 설정해도 무방)
• 알고 있는 모든 거리 값을 부여 (Python에서는 dictionary 객체를 이용하여 graph 표현)
• 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리를 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신
• 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거

import heapq  # 우선순위 큐 구현을 위함

def dijkstra(graph, start):
  distances = {node: float('inf') for node in graph}  # start로 부터의 거리 값을 저장하기 위함
  distances[start] = 0  # 시작 값은 0이어야 함
  queue = []
  heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작 하기 위함.

  while queue:  # queue에 남아 있는 노드가 없으면 끝
    current_distance, current_destination = heapq.heappop(queue)  # 탐색 할 노드, 거리를 가져옴.

    if distances[current_destination] < current_distance:  # 기존에 있는 거리보다 길다면, 볼 필요도 없음
      continue
    
    for new_destination, new_distance in graph[current_destination].items():
      distance = current_distance + new_distance  # 해당 노드를 거쳐 갈 때 거리
      if distance < distances[new_destination]:  # 알고 있는 거리 보다 작으면 갱신
        distances[new_destination] = distance
        heapq.heappush(queue, [distance, new_destination])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    
  return distances
  
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}
}

print(dijkstra(graph, 'A'))

 

---

최소 비용 (MST,  크루스칼 / 프림)

1) MST(Minimum Spanning Tree)

: 최소 비용 신장 트리( = 최소 신장 트리)를 뜻한다.

> 무방향 그래프의 간선들에 가중치가 주어진 경우, 여러 신장 트리 중 간선들의 가중치 합이 최소인 신장 트리

 

신장트리란?

• 신장 트리 : 무방향 그래프 G(V,E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프
• 신장 트리의 특징은 n개의 정점을 갖는 그래프에서 신장 트리에 속하는 간선의 수는 n-1개이며 사이클을 이루지 않는다는 특징이 있다.

---

2) 크루스칼(Kruskal) - MST 구하는 알고리즘

: greedy하게(결정의 순간마다 최선의 결정을 함으로써 최종적인 해답에 도달) 모든 정점을 최소 비용으로 연결하여 최소 신장 트리를 구함

1) 크루스칼의 핵심은 모든 간선을 가중치 기준으로 오름차순으로 정렬하고,

2) 간선들을 순서대로 모든 정점이 연결될 때까지 연결

>> Union-Find 알고리즘을 이용해서 구현할 수 있고, 이를 통해 사이클이 형성 안하면서 모든 정점 연결 가능

 

시간 복잡도 : O(ElogE)

//E : 간선의 개수

 

[크루스칼 알고리즘의 동작 방식]

1) 그래프의 간선들을 가중치 기준 오름차순으로 정렬

2)-1 정렬된 간선 리스트를 순서대로 선택하여, 간선의 정점들을 연결

2)-2 이때 정점을 연결하는 것은 Union-Find의 Union으로 구현

3) 만약 간선의 두 정점 a,b가 이미 연결되어 있다면 스킵

4) 위의 과정을 반복

 

> > 최소 비용의 간선들만 이용하여 모든 정점이 연결됨

import sys

v, e = map(int, input().split())
# 부모 테이블 초기화
parent = [0] * (v+1)
for i in range(1, v+1):
    parent[i] = i

# find 연산
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# union 연산
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 간선 정보 담을 리스트와 최소 신장 트리 계산 변수 정의
edges = []
total_cost = 0

# 간선 정보 주어지고 비용을 기준으로 정렬
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

# 간선 정보 비용 기준으로 오름차순 정렬
edges.sort()

# 간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행
for i in range(e):
    cost, a, b = edges[i]
    # find 연산 후, 부모노드 다르면 사이클 발생 X으므로 union 연산 수행 -> 최소 신장 트리에 포함!
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        total_cost += cost

print(total_cost)

---

3) 프림(Prim) - MST 구하는 알고리즘

: 임의의 시작점에서 현재까지 연결된 정점들에서 연결안된 정점들에 대해, 가장 가중치가 작은 정점을 연결하는 정점 선택 기반으로 동작

1) 프림의 핵심은 트리 집합을 단계적으로 확장하는 것이고, 

2) 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가

>> Priority Queue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사함

 

시간복잡도 : O(ElogV)

* E : 간선의 개수

* V : 정점의 개수

 

[프림 알고리즘 동작 방식]

1) 임의의 정점을 시작점으로 선택

2) 시작점에서 갈 수 있는 정점 중 가장 가중치가 작은 정점을 연결

3)-1 : 2번 과정에서 시작점과 어떠한 정점들이 연결됨

3)-2 : 시작점과 연결된 정점들을 a집합이라 할 때, a집합에서 갈수 있는 a집합에 속하지 않은 정점들에 대해 가중치가 가장 작은 정점 연결

4) a집합의 크기가 늘어남(시작점을 포함한 a집합에 새로운 정점을 연결함) 위의 과정을 모든 정점이 연결될 때까지 반복

 

import heapq
import collections
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, m = map(int,input().split()) # 노드 수, 간선 수
graph = collections.defaultdict(list) # 빈 그래프 생성
visited = [0] * (n+1) # 노드의 방문 정보 초기화

# 무방향 그래프 생성
for i in range(m): # 간성 정보 입력 받기
    u, v, weight = map(int,input().split())
    graph[u].append([weight, u, v])
    graph[v].append([weight, v, u])


# 프림 알고리즘
def prim(graph, start_node):
    visited[start_node] = 1 # 방문 갱신
    candidate = graph[start_node] # 인접 간선 추출
    heapq.heapify(candidate) # 우선순위 큐 생성
    mst = [] # mst
    total_weight = 0 # 전체 가중치

    while candidate:
        weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
        if visited[v] == 0: # 방문하지 않았다면
            visited[v] = 1 # 방문 갱신
            mst.append((u,v)) # mst 삽입
            total_weight += weight # 전체 가중치 갱신

            for edge in graph[v]: # 다음 인접 간선 탐색
                if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
                    heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입

    return total_weight

print(prim(graph,1))

[참고]

[Python] 최소 신장 트리를 찾는 크루스칼(Kruskal) 알고리즘

[알고리즘] 크루스칼(Kruskal)과 프림(Prim)

 

[알고리즘] 프림 알고리즘(Prim Algorithm)