그래프 최단거리

백준 1753 Dijkstra

기본 O(N^2), Heap 사용시 O(E*logV)

distance 저장용 1차원 Array 사용

import heapq
import sys
V, E = map(int, input().split())
K = int(input())

graph = [[] for _ in range(V +1)]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append((w,v))

dis = [1e9] * (V+1)


def Dijkstra(start):
    dis[start] = 0
    q = []
    heapq.heappush(q, (0,start))

    while q:
        dist, now = heapq.heappop(q)
        if dis[now] < dist:
            continue
        for wei, node in graph[now]:
            if dist + wei < dis[node]:
                dis[node] = dist + wei
                heapq.heappush(q, (dist+wei,node))

Dijkstra(K)
for i in range(1,V+1):
    print("INF" if dis[i] == 1e9 else dis[i])

 

백준 11404 Floyd

O(N^3), Distance 저장용 2차원 Array 사용

import sys

N = int(input())
E = int(input())
graph = [[1e9] * (N + 1) for _ in range(N + 1)]

for a in range(1, N + 1):
    for b in range(1, N + 1):
        if a == b:
            graph[a][b] = 0

for i in range(E):
    a, b, w = map(int, sys.stdin.readline().split())
    if graph[a][b] > w:			# 문제 조건에서 주어지는 여러 경로중 가장 짧은 경로만 저장
        graph[a][b] = w


def Floyd():
    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                graph[a][b] = min(graph[a][k] + graph[k][b], graph[a][b])


Floyd()
for a in range(1, N + 1):
    for b in range(1, N + 1):
        if graph[a][b] == 1e9:
            print("0", end=' ')
        else:
            print(graph[a][b], end=' ')
    print()

 

백준 1197 MST

Kruskal / Edge 정렬후 cost가 적은 edge순으로 node 연결- Cycle 확인(Union)

 

import sys
import heapq

def find_root(x, parent):
    if x != parent[x]:
        parent[x] = find_root(parent[x], parent)
    return parent[x]

def MST():
    v, e = map(int, input().split())
    edge = []
    Vroot = [i for i in range(v + 1)]
    path = 0
    for _ in range(e):
        u, v, w = map(int, sys.stdin.readline().split())
        edge.append((w, u, v))

    edge.sort(key=lambda x: x[2])

    for weight, start, end in edge:
        s_root = find_root(start, Vroot)
        e_root = find_root(start, Vroot)
        if s_root != e_root:
            if s_root < e_root:
                Vroot[e_root] = s_root
            if e_root < s_root:
                Vroot[s_root] = e_root
            path += weight

    print(path)

MST()