Jinho Tech

골드 3 난이도 치고는 쉬운 다익스트라 알고리즘 문제이다.

N-1개(1->X->1, 2->X->2, ..., N->X->X (X->X->X 제외))의 최단경로 중 최댓값을 출력해주면 된다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    dis = [INF]*(N+1)
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
    return dis[end]
    
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
t = 0
for i in range(1, N+1):
    if i == X:
        continue
    t = max(t, dijkstra(i, X) + dijkstra(X, i))
print(t)

기본적인 다익스트라 문제이긴 하다만, N-1번째 분기점을 제외하고 상대의 시야에 보이지 않는 분기점에만

방문해야 한다는 차이점이 있다.

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v] and check[v] == 0:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
check = list(map(int, input().split()))
check[-1] = 0
for _ in range(M):
    a, b, t = map(int, input().split())
    graph[a].append((b, t))
    graph[b].append((a, t))
dijkstra(0)
print(dis[N-1] if dis[N-1] != INF else -1)

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
dis = [INF]*(n+1)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
s, t = map(int, input().split())
dijkstra(s)
print(dis[t])

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
dijkstra(1)
print(dis[N])

너비 우선 탐색 or 다익스트라 문제인데 그냥 너비 우선 탐색으로 풀었다. 이전 숨바꼭질 문제와는 다르게 

순간이동할 때 걸리는 시간이 0이다. 이 점 때문에 node-1, node+1보다 node*2를 먼저 탐색을 해줘야 한다.

node*2를 node+1 보다 나중에 탐색해버리면 시작 노드가 1일 때 노드 2의 값이 0이 아닌 1이 되어버려서 틀린다.

from collections import deque

def bfs(N, K):
    queue = deque([N])
    graph[N] = 0
    while queue:
        node = queue.popleft()
        if node == K:
            return ;
        for n in [node*2, node-1, node+1]:
            if (0 <= n <= 100000) and graph[n] == -1:
                queue.append(n)
                graph[n] = graph[node] + (0 if n == node*2 else 1)
            
N, K = map(int, input().split())
graph = [-1]*100001
bfs(N, K)
print(graph[K])

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
                
N, M = int(input()), int(input())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
s, e = map(int, input().split())
dijkstra(s)
print(dis[e])

다익스트라 문제이긴 한데 조금 더 쉽게 풀 수 있는 문제이다. BFS랑 매우 비슷한 풀이다.

1. 최단거리 테이블 생성 -> [i for i in range(D+1)] = [0, 1, 2, 3, ... , D]

2. 한 칸 전 위치의 테이블 값+1이 현재 테이블 값보다 작다면 현재 테이블 값을 한 칸 전 위치의 테이블 값+1로 바꾼다. 

3. 현재 위치에 지름길이 있다면 지름길로 건너간 곳의 원래 테이블 값과 지름길로 건너가기 전의 테이블 값+지름길의 거리 중 더 작은 값으로 건너간 곳의 값을 바꾼다. 

N, D = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
dis = [i for i in range(D+1)]
for i in range(D+1):
    if i > 0:
        dis[i] = min(dis[i], dis[i-1]+1)
    for s, e, d in li:
        if i == s and e <= D and dis[i]+d < dis[e]:
            dis[e] = dis[i]+d
print(dis[D])

기본적인 다익스트라 문제이다.

다익스트라를 1(맨 처음 노드), v1, v2 기준으로 3번 돌려서 3개의 최단 거리 테이블을 생성하고

1 -> v1 -> v2 -> n 순서로 갈 때와 1 -> v2 -> v1 -> n 순서로 갈 때의 거리 중 더 짧은 길이를 출력해주면 된다.

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis = [INF]*(N+1)
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
    return dis

N, E = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(E):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
v1, v2 = map(int, input().split())
d1 = dijkstra(1)
d2 = dijkstra(v1)
d3 = dijkstra(v2)
res = min(d1[v1]+d2[v2]+d3[N], d1[v2]+d3[v1]+d2[N])
print(res if res < INF else -1)

다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.

간선에 가중치가 없다면 너비 우선 탐색(BFS)으로도 충분히 풀 수 있지만, 간선에 가중치가 있다면 풀기가 매우

힘들어진다. 간선에 가중치가 있다면 다익스트라 알고리즘을 사용해서 풀도록 하자!!

다익스트라 알고리즘은 동작 과정은 아래와 같다.

1. 출발 노드 지정

2. 최단 거리 테이블 초기화

3. 방문한 적 없는 노드 중에서 최단 거리가 제일 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 거리를 구하여 최단 거리 테이블을 업데이트

5. 위 3, 4번 과정을 모든 노드를 방문할 때까지 반복

아래 코드는 파이썬으로 구현한 다익스트라 알고리즘 예시이다.

백준 1753번 최단경로)

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

V, E = map(int, input().split())
start = int(input())
INF = 10**9
dis = [INF]*(V+1)
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
dijkstra(start)
for n in dis[1:]:
    print(n if n != INF else "INF")

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1011

jinho-study.tistory.com/1013

jinho-study.tistory.com/1014

jinho-study.tistory.com/1015

jinho-study.tistory.com/1021

jinho-study.tistory.com/1022

jinho-study.tistory.com/1023

jinho-study.tistory.com/1069

기본적인 다익스트라 알고리즘 문제이다. 

import heapq
import sys
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

V, E = map(int, input().split())
start = int(input())
INF = 10**9
dis = [INF]*(V+1)
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
dijkstra(start)
for n in dis[1:]:
    print(n if n != INF else "INF")