백준(1753,1916,1854)
다익스트라 알고리즘
최단 경로 구하기(1753)
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
- 입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
- 입출력 예시
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
--------------
0
2
3
7
INF
해결책
최단경로 A → B를 구할 수 있는 알고리즘인 다익스트라 알고리즘을 활용한다.
기본적으로 다익스트라 알고리즘은 최단경로배열, 방문배열을 사용한다.
최초 최단경로배열은 시작점은 최단경로가 0이므로, 0으로 초기화하고 나머지 노드들은 가장큰 값으로 초기화한다. sys.maxsize를 이용한다.
시작점을 기준으로 가장 작은 최단경로를 가지는 노드를 선택하는 방식으로 그래프 탐색하므로, 가장작은 노드를 찾는과정에서 우선순위큐를 사용하여 시간복잡도를 줄일 수 있다. 큐에 진입시키는 노드는 [최단경로, 노드정보]로 구성하여, 최단경로를 기준으로 최소힙을 구현할 수 있도록 한다.
방문 노드 체크는 우선순위큐에서 dequeue했을때 기준으로 진행시킨다.
코드
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
inf = sys.maxsize
n,m = map(int , input().split())
start = int(input())
maps = [[] for _ in range(n+1)]
dist = [inf]*(n+1)
visited = [0] * (n+1)
dist[start]= 0
for i in range(m):
s,e,w = map(int, input().split())
maps[s].append([e,w])
heap= []
heappush(heap,[0,start])
while heap :
minnode=heappop(heap)
if visited[minnode[1]]==1 :
continue
visited[minnode[1]]=1
for k in maps[minnode[1]]:
if dist[k[0]] > dist[minnode[1]]+k[1]:
dist[k[0]]=dist[minnode[1]]+k[1]
heappush(heap,[dist[k[0]],k[0]])
for i in range(1,len(dist)) :
if visited[i] :
print(dist[i])
else :
print("INF")
최소 비용 구하기(1916)
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.
- 입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
- 입출력 예시
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5
--------------
4
해결책
이문제 또한, 1753번 문제와 동일한 다익스트라 알고리즘으로 풀이가 가능한 문제이다.
최단경로 A → B를 구할 수 있는 알고리즘인 다익스트라 알고리즘을 활용한다.
기본적으로 다익스트라 알고리즘은 최단경로배열, 방문배열을 사용한다.
최초 최단경로배열은 시작점은 최단경로가 0이므로, 0으로 초기화하고 나머지 노드들은 가장큰 값으로 초기화한다. sys.maxsize를 이용한다.
시작점을 기준으로 가장 작은 최단경로를 가지는 노드를 선택하는 방식으로 그래프 탐색하므로, 가장작은 노드를 찾는과정에서 우선순위큐를 사용하여 시간복잡도를 줄일 수 있다. 큐에 진입시키는 노드는 [최단경로, 노드정보]로 구성하여, 최단경로를 기준으로 최소힙을 구현할 수 있도록 한다.
방문 노드 체크는 우선순위큐에서 dequeue했을때 기준으로 진행시킨다.
코드
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
inf = sys.maxsize
n = int(input())
m = int(input())
dist=[inf]*(n+1)
visited=[0] * (n+1)
maps = [[] for _ in range(n+1)]
heap =[]
for i in range(m):
s, e , w = map(int,input().split())
maps[s].append([e,w])
start,end = map(int,input().split())
dist[start]=0
heappush(heap,[0,start])
while heap :
pnode=heappop(heap)
if visited[pnode[1]]:
continue
visited[pnode[1]] =1
for nnode in maps[pnode[1]] :
if dist[nnode[0]] > dist[pnode[1]]+nnode[1]:
dist[nnode[0]] = dist[pnode[1]]+nnode[1]
heappush(heap, [dist[nnode[0]],nnode[0]])
print(dist[end])
K번째 최단 경로 찾기(1854)
봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, ‘느림의 미학’을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 ‘k번째 최단경로’를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.
- 입력
첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.
이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000)
도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.
- 입출력 예시
5 10 2
1 2 2
1 3 7
1 4 5
1 5 6
2 4 2
2 3 4
3 4 6
3 5 8
5 2 4
5 4 1
--------------
-1
10
7
5
14
해결책
이 문제는 위의 두 문제와 다르게, k번째 최단경로를 구해야하는 문제가 있다.
이문제의 핵심은
-
최단경로만을 구하는 것이 아닌, k번째 최단경로를 구해야하므로, 노드들을 수차례 방문해야한다는 것이다. 그러므로, 방문여부를 체크하는 로직을 제외해야한다.
-
k번째 최단경로는 한번에 구할 수 없다. 최소 k번의 최단경로를 구해야한다.
그러므로, 단일리스트가 아닌 이중리스트를 통해 그때 그때 구한 경로값과 k번째의 최단경로 값과 비교하여 k번째에 write하고, 그 리스트를 정렬해야하며, 또한 큐에 다시 재진입시키는 형식으로 해결하면된다.
노드진입시 위의 문제들과 동일하게 수정이 될 수 있는 경우에만
[ 최신화된 거리, nextNode]로 진입시켜주면된다.
코드
import sys
from heapq import heappop, heappush
input = sys.stdin.readline
inf = sys.maxsize
n,m,k = map(int ,input().split())
maps = [[] for _ in range(n+1)]
dist=[ [inf]*k for _ in range(n+1)]
for i in range(m):
s,e,w = map(int,input().split())
maps[s].append([e,w])
heap=[]
dist[1][0]=0
heappush(heap,[0,1])
while heap :
pnode=heappop(heap)
for nnode in maps[pnode[1]] :
if dist[nnode[0]][k-1] > pnode[0]+nnode[1]:
dist[nnode[0]][k-1] = pnode[0]+nnode[1]
dist[nnode[0]].sort()
heappush(heap, [pnode[0]+nnode[1],nnode[0]])
for i in range(1,n+1):
if dist[i][k-1] == inf :
print("-1")
else :
print(dist[i][k-1])
댓글남기기