MST, Dijkstra

간선의 개수를 최소화하면서 모든 정점을 연결하는 방법

1. 여러방법이 있다.
2. 싸이클이 발생하지 않는다.
3. 간선의 개수 = V -1 개

=⇒ 신장 트리

문제 해결방법

1. 완탐 (가짓수가 너무 많다): X
2. 백트래킹 (가지를 칠 조건이 하나밖에 없다) : X
3. Dp, 그리디 등등
4. 제일 작은것 부터 고르는 그리디
5. 특정 노드를 시작으로 갈수 있는 곳들 중 작은 곳만 가자

Prim 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중(=bfs, queue) 에 최소 비용(=우선순위)의 간선이 존재하는 정점을 선택

⇒ 우선순위 + 큐 = 우선순위 큐 == > heapq를 사용한다.

input

'''
서울(0),천안(1),원주(2),논산(3),대전(4),
대구(5),강릉(6),광주(7),부산(8),포항(9)
'''
'''
9 14
0 1 12
0 2 15
1 3 4
1 4 10
2 5 7
2 6 21
3 4 3
3 7 13
4 5 10
5 8 9
5 9 19
6 9 25
7 8 15
8 9 5
'''

 

알고리즘 코드 1

import sys;sys.stdin=open('input.txt',"r")
from heapq import heappush,heappop # 우선순위 큐라서 사용해야 한다.
'''

'''

def prim(start):
    # priorityque
    pq = []
    MST = [0] * V # visited 역할

    # 최소 비용
    sum_weight = 0

    # 시작점 추가
    '''
    [기존 BFS] 노드 번호만 관리
    [Prim] 가중치가 낮으면 먼저 나와야 한다.
    -> 관리해야할 데이터 : 가중치, 노드 번호
    -> 동시에 두가지 데이터 다루기
        1. class 로 만들기
        2. 튜플로 관리
    이차원배열 + 가중치 + 높이 라면? 튜플로 관리하기 어렵다.
    => 3가지 이상으로 클래스로 해야한다.
    '''
    heappush(pq, (0,start))

    while pq:
        weight, now = heappop(pq)
        '''
        # 우선순위 큐의 특성 상,
        # 더 먼거리로 가는 아법이 큐에 저장이 되어 있기 때문에
        # 기존에 이미 더 짧은 거리로 방문했다면, continue
        '''
        # 방문 했다면 continue
        if MST[now]:
            continue
        # 방문 처리
        MST[now] = 1
        # 누적 합 추가
        sum_weight += weight

        # 갈수 있는 노드들을 보면서
        for to in range(V):
            if graph[now][to] == 0 or MST[to]: # 합친것
               continue

            '''
            # 갈 수 없다면 pass
            if graph[now][to] == 0:
                continue
            # 이미 방문했다면 pass
            if MST[to]:
                continue
            '''
            heappush(pq, (graph[now][to],to))

    print(f'최소비용 : {sum_weight}')
V, E = map(int,input().split())
# 인접 행렬로 저장
# - [실슴] 인접 리스트로 저장
graph = [[0] * V for _ in range(V)]
for _ in range(E):
    s,e,w = map(int,input().split())
    # 가중치 저장
    '''
    # [기존] 3~4 로 갈 수 있다.
    graph[3][4] = 1

    # [가중치 그래프] 3-> 4 로 가는데 31이라는 비용이 든다.
    graph[3][4] = 31
    '''
    graph[s][e] = w
    graph[e][s] = w  # 무방향 그래프
print(graph)
prim(0)
'''
BFS : 무조건 방문
PRIM : 일단 pq에 넣고 방문 X
'''

 

알고리즘 코드 2

import sys;sys.stdin = open('input.txt')
# 힙 사용없는 우선순위 큐
# visited 와 최소값만 구할 줄 알면 된다.
def prim(s):
    # 출발점 설정
    D[s] = 0
    total = 0
    for _ in range(V+1): # 모든 도시를 선택
        # 가중치 최소 값 찾기
        min_v = INF
        for i in range(V+1):
            if visited[i] == 0 and min_v > D[i]:
                min_v = D[i]
                v = i

        # 방문 처리
        visited[v] = 1 # 다음번에 찾을 때 다시 안 구하기 위해서
        total += adj[PI[v]][v] # total += adj[부모][현재]

        # 인접도시 업데이트
        for w in range(V+1):
            if adj[v][w] and not visited[w]:
                if D[w] > adj[v][w]:
                    D[w] = adj[v][w]
                    PI[w] = v
    return total

V, E = map(int,input().split())
adj = [[0]*(V+1) for _ in range(V+1)] # 인접행렬
INF = int(1e9)
D = [INF] *(V+1)                # 가중치
PI = [i for i in range(V+1)]    # 부모
visited = [0] * (V+1)           # 방문

for i in range(E):
    s, e, w = map(int,input().split()) # 시작 , 끝,  가중치
    adj[s][e] = adj[e][s] = w          # 무향 그래프라서
print(prim(0))

 

Krual 알고리즘

알고리즘

import sys;sys.stdin = open('input.txt')
'''
1. 전체 그래프를 보고, 가중치가 제일 작은 간선부터 뽑자
    -> 코드로 구현: 전체 간선 정보를 저장 + 가중치로 정렬

2. 방문 처리
    -> 이 때, 싸이클이 발생하면 안된다!
    -> 싸이클 여부 ?? => union-find 알고리즘이 활용
'''

def find_set(x):
    if parents[x] == x:
        return x
    # 경로 압축
    parents[x] = find_set(parents[x])
    return parents[x]

def union(x,y):
    x = find_set(x)
    y = find_set(y)

    # 같은 집합이면 pass
    if x == y:
        return

    if x < y:
        parents[y] = x
    if x > y:
        parents[x] = y

V, E = map(int,input().split())
# 인접 리스트
edges = []

for _ in range(E):
    s,e,w = map(int,input().split())
    edges.append([s,e,w])

edges.sort(key=lambda x:x[2]) # 가중치를 기준으로 정렬
parents = [i for i in range(V)] # 대표자 배열 ( 자기 자신을 바라봄

# MST 완성 = 간선의 개수가 V-1 개 일 때
cnt = 0
sum_weight = 0

# 간선들을 모두 확인한다.
for s,e,w in edges:
    # 싸이클이 발생하면 pass
    #-> 이미 같은 집합에 속해 있다면 pass
    if find_set(s) == find_set(e):
        print(s,e,w, '싸이클 발생! 탈락!')
        continue
    print(s,e) # 유니온 순서 확인하기
    cnt += 1
    # 싸이클이 없으면 통과, 방문 처리
    union(s,e)
    sum_weight += w

    if cnt == V: # MST 완성! 간선의 개수 == V-1
        break
print(f'최소 비용 : {sum_weight}')
print(cnt)

 

최단경로

전체를 연결(MST)하는게 아닌 두 정점 사이의 경로들 중에서 고르기

from heapq import heappop,heappush

INF = int(1e9) # 무한을 의미하는 값으면 10억
V, E = map(int,input().split())
start = 0 # 시작 노드 번호

# 인접 리스트
graph = [[] for _ in range(V)]
# 누적 거리를 저장할 변수 - INF 로 저장
distance = [INF] * V

# 간선 정보 저장
for _ in range(E):
    s, e, w = map(int,input().split())
    '''
    graph[3][4] = 34 # 인접 행렬 형식
    graph[3] = [[4,31]] # 인접 리스트 형식
    '''
    graph[s].append([e,w])

def dijkstra(start):
    pq = []
    # 시작 노드 최단 거리는 0
    # 시작점의 weight, node 번호를 한 번에 저장
    # heapq 에 리스트로 저장할 때는 맨 앞의 데이터를 기준으로 정렬된다.
    heappush(pq, (0, start))

    # 시작 노드 초기화
    distance[start] = 0

    # 우선순위 큐가 빌 때 까지 반복
    while pq:
        # 최단 거리 노드에 대한 정보 꺼내기
        dist, now = heappop(pq)

        # pq 의 특성 때문에 더 간거리가 미리 저장되어 있음
        # now 가 이미 더 짧은 거리로 온 적이 있다면 pass
        # == 현재 노드가 이미 처리됐다면 skip
        if distance[now] < dist:
            continue

        # now(현재 노드) 에서 인접한 다른 노드 확인
        for to in graph[now]:
            next_node = to[0]
            next_dist = to[1]

            # 누적 거리 계산
            new_dist = dist + next_dist

            # 이미 더 짧은 거리로 간 경우 pass
            if new_dist >= distance[next_node]:
                continue

            distance[next_node] = new_dist # 누적 거리르 최단 거리로 갱신
            heappush(pq, (new_dist, next_node)) # next_node의 인접 노드들을 추가
# 실행
dijkstra(start)
# print(distance)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(V):
    # 도달할 수 없는 경우, 무한 출력
    if distance[i] == INF:
        print("INF", end=' ')
    else:
        print(distance[i], end=' ')