8주차 스터디 그래프 이론 - 백준 1916번 최소비용 구하기

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

IDEA

버스의 출발도시 , 도착도시 , 버스 비용이 차례대로 주어지고 , 출발점의 도시번호로부터 도착점의 도시번호까지 가는 최소비용을 구하는 문제다. 즉, 한 점에서 다른 한 점까지 가는 최소비용을 구하는 문제이다. 

다른 풀이법도 있을 수 있겠지만, 한 점에서 모든 정점까지 가는 최소비용을 구할 수 있는 다익스트라 알고리즘을 이용해서 풀었다. 다익스트라 알고리즘의 대표예제 수준인 문제라서 어렵진 않다. 

아 최근에 파이썬 공부를 하는데 c++을 까먹을까봐 두 번 풀려고 노력하는 중이다.

 

CODE - C++ 

#include <iostream>
#include <vector>
#include<algorithm>
#include<queue>

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; //거리 , 인덱스
vector<vector<pair<int, int>>> graph;

int cost[1005] = { 0 };
bool visited[1005] = { false };
int v, e, sx , sy; // 정점의 개수 , 입력의 개수 ,출발지점, 도착지점

int dijkstra() {
	q.push({ 0,sx });
	visited[sx] = true;
	while (!q.empty()) {
		int cur_c = q.top().first;
		int cur_s = q.top().second;
		q.pop();
		if (cur_s == sy) return cost[cur_s];
		for (int i = 0; i < graph[cur_s].size(); i++) {
			int next_d = graph[cur_s][i].second;
			int next_c = graph[cur_s][i].first;
			if (cost[next_d] > cur_c + next_c) {
				cost[next_d] = cur_c + next_c;
				if (!visited[next_d]) q.push({ cost[next_d] , next_d });
			}
		}
	}
}

int main() {
	cin >> v >> e;
	graph.resize(v + 1);
	for (int i = 0; i < e; i++) {
		int depart, arrive, c;
		cin >> depart >> arrive >> c;
		graph[depart].push_back({ c, arrive });
	}
	
	cin >> sx >> sy;
	fill(cost, cost + v + 1, 987654321);
	cost[sx] = 0;

	printf("%d" , dijkstra());
}

 

CODE - Python

import sys
input = sys.stdin.readline

from heapq import heappush , heappop

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
cost = [987654321 for _ in range(n+1)]

for i in range(m) : 
  a,b,c = map(int,input().split())
  graph[a].append([c,b])
start , end = map(int,input().split())

def dijkstra(start , end):
  heap = []
  heappush(heap,[0,start]) # cost ,노드
  cost[start] = 0

  while heap:
    cur_cost , cur_node = heappop(heap)
    if (cur_node == end) : return cost[cur_node]
    for new_cost , new_node in graph[cur_node]:
      if (cost[new_node] > cost[cur_node] + new_cost) : 
        cost[new_node] = cost[cur_node] + new_cost
        heappush(heap,[cost[new_node] ,new_node])

print(dijkstra(start , end))

 

➕➕

성격이 급해서 문제다. 

다익스트라 함수 내에서 도착지점을 만나면 return 하는 한 줄의 차이에 대해서 말하려고 캡쳐해봤다. 

똑같은 코드로 return 문이 없을 때는 336ms , 있을 때는 248m로 대략 100ms가 차이난다.