졍's 기술 블로그

최소비용 구하기

티어 : Gold 5
시간 제한 : 0.5 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 다익스트라

문제

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째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 입력으로 graph 구성
2. 다익스트라 알고리즘을 이용해 최단 경로 구하기

Code

import sys
import heapq

def dijkstra(start):
    queue = []
    
    # 첫 번째 위치 큐에 추가
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    while queue:
        # queue에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 이미 방문한 적 있는 도시이면 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            # cost 계산 : 현재 node의 누적 거리 + 현재 노드에서 다음 노드까지의 거리
            cost = dist + next[0]
            # cost가 distance에 저장된 값보다 작으면 갱신
            if cost < distance[next[1]]:
                distance[next[1]] = cost
                heapq.heappush(queue, (cost, next[1]))
                
input = sys.stdin.readline
INF = 1e9

# 입력
N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)
for _ in range(M):
    start, end, cost = map(int, input().split())
    graph[start].append((cost, end))
start, end = map(int, input().split())

dijkstra(start)
print(distance[end])

메모리: 56088 KB
시간: 352 ms

최단경로

티어 : Gold 5
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 그래프 이론, 다익스트라

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 입력으로 graph 구성
2. 다익스트라 알고리즘을 이용해 최단 경로 구하기

Code

import sys
import heapq

def dijkstra(start):
    queue = []
    # 첫 번째 노드 큐에 추가
    heapq.heappush(queue, (0, start))
    distance[start] = 0
    
    while queue:
        # 큐에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 이미 방문한 노드는 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            # cost 계산 = 현재 node의 거리 + 다음 node까지의 거리
            cost = dist + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                # 큐에 추가
                heapq.heappush(queue, (cost, next[0]))

INF = int(1e9)
input = sys.stdin.readline

V, E = map(int, input().split())
start = int(input())
graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1)
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

dijkstra(start)
for i in range(1, V+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

메모리: 66936 KB
시간: 700 ms

지름길

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 다이나믹 프로그래밍, 그래프 이론, 다익스트라

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제 입출력

Algorithm

dijkstra 알고리즘 - 힙
1. 지름길을 입력 받아 graph 생성
    ➝ 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
2. 지름길이 아닌 길도 graph에 추가
    ➝ 중간에 끊겨있는 길도 같이 추가
3. D 위치의 최단 거리 출력

Code

import sys
import heapq

INF = int(1e9)
input = sys.stdin.readline

def dijkstra(start):
    queue = []
    
    # 첫 번째 칸으로 가는 최단 경로 0으로 설정
    heapq.heappush(queue, (start, 0))
    distance[start] = 0
    
    while queue:
        
        # 큐에서 꺼내기
        dist, now = heapq.heappop(queue)
        
        # 방문한 노드라면 무시
        if distance[now] < dist:
            continue
        
        # 인접 노드 확인
        for next in graph[now]:
            cost = dist + next[1]
            
            # cost가 인접노드까지 가는 데 최소 거리라면 갱신하고 큐에 추가
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(queue, (cost, next[0]))
    

N, D = map(int, input().split())
graph = [[] for _ in range(D+1)]
distance = [INF] * (D+1)
for _ in range(N):
    start, end, length = map(int, input().split())
    # 도착 지점이 고속도로의 길이보다 큰 경우 graph에 추가하지 않음
    if end > D:
        continue
    graph[start].append((end, length))

    # 지름길이 아닌 길도 graph에 추가
    if (end, end - start) not in graph[start]:
        graph[start].append((end, end - start))
        
for i in range(D):
    # graph의 현재 INDEX에 다음 칸 까지의 거리 추가
    graph[i].append((i+1, 1))

dijkstra(0)
print(distance[-1])

메모리: 32928 KB
시간: 72 ms