✅ BOJ
🎈 13305 주유소
N개의 도시가 있고, 도시들 간의 일직선 도로가 존재한다. 도로 간 이동 거리가 주어지고 1km당 1리터의 기름을 사용한다.
처음 출발 시 차에 기름이 없을 때, 제일 왼쪽 도시에서 오른쪽 도시로 이동하는 최소 비용을 계산하는 프로그램 작성하기.
import sys
input = sys.stdin.readline
n = int(input())
dists = list(map(int, input().split()))
costs = list(map(int, input().split()))
price = costs[0]
answer = 0
for i in range(n-1):
if price > costs[i]:
price = costs[i]
answer += price * dists[i]
print(answer)< 풀이 과정 >
도시 내 주유소 별 비용을 이용해 계산하는 문제.
n-1 도시보다 n 도시의 주유소 비용이 더 비싸면 n-1 도시에서 n-1 도시 -> n+1 도시로 이동하는 거리까지 n-1 도시에서 주유를 하면 되는 문제.
이를 그대로 구현만 해주면 된다.
초기에 차에 기름이 없으므로 default로 무조건 0번 도시에서 1번 도시까지의 이동 과정은 무조건 0번도시의주유비 * 1번도시까지의이동거리 만큼의 비용이 발생하게 된다.
🎈 13308 주유소
13305와 유사한 문제. 그러나 다음과 같이 도시가 주어지며 도시 이동 간 비교가 필요하다.
입력값은 다음과 같다.
- 첫 줄에 도시수, 도로수
- 다음 줄에 각 도시 별 주유소의 리터 당 가격
- 도로 수만큼 줄이 생성되며 (출발도시, 도착도시, 도시간거리)가 주어진다.
- 도시 간 도로는 양방향 공유
import sys, heapq
input = sys.stdin.readline
n, m = map(int, input().split())
costs = [-1] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
def dijkstra():
# 상태공간 visited[node][cost] : 현 노드가 node, 단위 비용이 cost
visited = [[float('infinity')] * (max(costs)+1) for _ in range(n+1)]
heap = []
visited[1][costs[1]] = 0
# 초기 발생한 비용, 시작 노드 -> 다음 노드 이동 시 발생하는 단위 비용, 현 노드
heapq.heappush(heap, (0, costs[1], 1))
while heap:
now_dist, now_cost, now = heapq.heappop(heap)
# 노드가 목적지 노드와 일치하면 발생 비용 리턴
if now == n:
return now_dist
# 현 노드의 현재 비용으로 더 짧은 거리 방문하면 무시 (무한대 2차원 그래프이므로)
if visited[now][now_cost] < now_dist:
continue
# 인접 노드들의 노드, 필요 이동 거리 비교
for next, next_dist in graph[now]:
# 다음 노드로 도착해서 사용할 단위 비용
next_cost = min(costs[next], now_cost)
# 현재 총 비용이 다음 정점 가는 데 드는 비용보다 작으면 heapq에 삽입.
if visited[next][next_cost] > now_dist + now_cost * next_dist:
visited[next][next_cost] = now_dist + now_cost * next_dist
heapq.heappush(heap, (now_dist + now_cost*next_dist, next_cost, next))
print(dijkstra())< 풀이 과정 >
고난이도 다익스트라를 구현한 문제.
주어진 노드를 순서대로 탐색하는 문제가 아니기에 다익스트라 함수를 별도로 구현하여 생성하였다. 뭐 입력값이야 들어오는대로 처리를 해주고, 다만 도시 별 리터당 주유 비용 리스트는 그래프 크기 역시 (도시수 + 1이므로), 인덱스 일치를 위해 맨 앞단에 -1을 추가해준다.
- graph : 각 노드 별 연결된 노드와 간선(필요 이동 거리 저장)
- visited : 각 노드 별 단위 이동 비용 (상태 공간 의미)
- heap : 현재 노드까지 드는 비용, 다음 노드 이동 시 드는 비용, 현재 노드
다익스트라 함수는 다음과 같다.
1. 도시별 리터당 주유비 리스트 : 인덱스 일치를 위해 제일 앞에 -1 입력
2. 빈 그래프 : graph[i]는 노드 i와 연결된 노드, 간선 정보
3. 다익스트라 함수 생성하여 visited 2차원 무한대 그래프와 힙 구현을 위한 빈 리스트 생성
4. visited[now][cost] : 현 노드에 드는 단위 비용을 의미 ,초기값은 무한대로 지정.
5. for문을 돌며 다음 노드에 드는 비용을 상태공간에 저장된 현재 비용과 비교하며 상태공간이 더 크면 값을 최소로 개선해주며 heap에 삽입해주는 문제
