Jinho Tech

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

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])

기본적인 플로이드-와샬 문제이다.

graph[a][k] == 1 and graph[k][b] == 1 이면 a에서 b로 갈 수 있다라는 점이 핵심이다.

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] and graph[k][b]:
                graph[a][b] = 1
for line in graph:
    print(*line)

기본적인 플로이드-와샬 문제이다. PyPy3로 제출해야 통과된다.

(특정 노드가 다른 노드를 가리키는 횟수 + 다른 노드가 특정 노드를 가리키는 횟수) == N-1이라면

그 특정 노드의 순서를 알 수 있다는 점이 핵심이다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] == 1 and graph[k][b] == 1:
                graph[a][b] = 1
res = 0
for i in range(N):
    t = 0
    for j in range(N):
        t += graph[i][j] + graph[j][i]
    if t == N-1:
        res += 1
print(res)

다익스트라 알고리즘 같은 경우에는 하나의 정점에서 출발해서 모든 정점으로의 최단거리를 구할 수 있는 반면에,

플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구할 수 있다.

이 알고리즘의 핵심은 거쳐가는 정점을 기준으로 최단거리를 구한다는 점이다.

다익스트라에 비해서 구현 난이도가 훨씬 쉽다! 와!! 삼중 반복문!!!

아래 코드는 파이썬으로 구현한 플로이드-와샬 알고리즘 예시이다.

백준 11404번 플로이드)

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

n, m = int(input()), int(input())
dis = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c < dis[a-1][b-1]:
        dis[a-1][b-1] = c
for k in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                dis[a][b] = min(dis[a][b], dis[a][k]+dis[k][b])
for i in range(n):
    for j in range(n):
        if dis[i][j] == INF:
            dis[i][j] = 0
for t in dis:
    print(*t)

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1017?category=911939

jinho-study.tistory.com/1019

jinho-study.tistory.com/1020

https://jinho-study.tistory.com/1085

기본적인 플로이드-와샬 문제이다. 

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

n, m = int(input()), int(input())
dis = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c < dis[a-1][b-1]:
        dis[a-1][b-1] = c
for k in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                dis[a][b] = min(dis[a][b], dis[a][k]+dis[k][b])
for i in range(n):
    for j in range(n):
        if dis[i][j] == INF:
            dis[i][j] = 0
for t in dis:
    print(*t)

너비 우선 탐색 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")

우선순위 큐를 사용해서 빠르게 중앙값을 찾아야 되는 문제이다.

우선순위 큐를 2개(최대 힙, 최소 힙) 사용한다는 점이 핵심이다. 왼쪽 우선순위 큐는 최대 힙으로 최댓값이 맨 처음에

오도록 구현하고, 오른쪽 우선순위 큐는 최소 힙으로 최솟값이 맨 처음에 오도록 구현한다.

왼쪽과 오른쪽 우선순위 큐의 크기가 똑같다면 왼쪽 우선순위 큐에 값을 저장하고, 왼쪽 우선순위 큐의 첫 번째 값이

오른쪽 우선순위 큐의 첫 번째 값보다 큰 경우가 생기면 왼쪽 값을 오른쪽 값으로 바꿔주면 된다.

마지막에는 왼쪽 우선순위 큐의 맨 처음 값(최대 힙의 최댓값)을 출력해주면 된다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
leftq, rightq = [], []
for _ in range(N):
    n = int(input())
    if len(leftq) == len(rightq):
        heapq.heappush(leftq, (-n, n))
    else:
        heapq.heappush(rightq, (n, n))
    if rightq and leftq[0][1] > rightq[0][1]:
        left, right = heapq.heappop(leftq)[1], heapq.heappop(rightq)[1]
        heapq.heappush(leftq, (-right, right))
        heapq.heappush(rightq, (left, left))
    print(leftq[0][1])

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, (abs(n), n))
    else:
        print(heapq.heappop(q)[1] if q else 0)

우선순위 큐(Priority Queue)는 큐(Queue)나 스택(Stack)과 비슷한 축약 자료형이다.

일반적인 큐는 FIFO(First in-First Out) 구조이지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 

우선순위가 높은 데이터가 먼저 나오는 구조이다.

파이썬에서는 heapq 또는 PriorityQueue 라이브러리를 사용해서 우선순위 큐를 구현할 수 있다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
    heapq.heappush(heap, n)
while heap:
    print(heapq.heappop(heap))

heapq.heappush를 사용해서 우선순위 큐에 요소를 삽입하고, heapq.heappop을 사용해서 pop 할 수 있다.

heapq는 기본적으로 최소 힙이라서 값이 작은 (1, 3)부터 (3, 1), (10, 2)가 순서대로 pop 되는 것을 확인할 수 있다.

큰 것부터 pop 하고 싶다면 아래 코드와 같이 구현해주면 된다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
    heapq.heappush(heap, (-n, n))
while heap:
    print(heapq.heappop(heap)[1], end=' ')
print()

아래 코드는 PriorityQueue를 사용해서 구현한 우선순위 큐이다.

from queue import PriorityQueue

q = PriorityQueue(maxsize=4)
q.put(3)
q.put(7)
q.put(2)
q.put(9)
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')

우선순위 큐는 다익스트라 알고리즘이나, K번 째 최댓값을 찾을 때 등등에 사용할 수 있다.

아래는 대표적인 우선순위 큐 문제 풀이이다.

백준 11279번 최대 힙)

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, -n)
    else:
        print(-heapq.heappop(q) if q else 0)

백준 1927번 최소 힙)

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, n)
    else:
        print(heapq.heappop(q) if q else 0)

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1006

jinho-study.tistory.com/1007

jinho-study.tistory.com/1009

jinho-study.tistory.com/1010

jinho-study.tistory.com/1024

jinho-study.tistory.com/1026

jinho-study.tistory.com/1027

jinho-study.tistory.com/1067

jinho-study.tistory.com/1068

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, n)
    else:
        print(heapq.heappop(q) if q else 0)