BFS : 최소비용 구하기(백준 1916번)

▶ 문제 : https://www.acmicpc.net/problem/1916

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

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

 

▶ 접근 방법

최소 비용을 구하기 위해서 다익스트라 알고리즘을 이용했다.
다익스트라 알고리즘에서 최단 거리 찾는 방법을 적용하면
문제에서 요구하는 최소 비용을 쉽게 구할 수 있다.
다익스트라 알고리즘의 기본 개념은 아래 관련 링크를 통해 확인할 수 있다.

처음 그래프를 형성하고 각 경로 별 비용을 그래프에 넣어주는 것,
최단 경로 테이블, 문제에서는 최소 비용 테이블을 만들어 주는 것이 문제 해결에 있어 중요했다.

 

▶ 풀이 코드

import sys, heapq

# 전체 도시의 수 
num_of_city = int(input())

# 도시들을 오가는 버스의 수 
num_of_bus = int(input())

# 도시의 수를 고려하여 graph를 만든다.
graph = [[] for _ in range(num_of_city + 1)]

# 최단 경로 테이블(여기서는 최소 비용 테이블)을 리스트로 만든다.
# 무한대 값은 int(1e9)로 설정해준다.
cost_table = [int(1e9)] * (num_of_city + 1)

# graph에 출발 도시와 도착 도시, 버스 비용을 표현해준다.
# 여기서는 리스트로 구현했다.
for _ in range(num_of_bus):
    start_city, end_city, fee = map(int,sys.stdin.readline().split())
    graph[start_city].append((end_city, fee))
# print(graph)

# 출발 도시와 도착 도시를 입력받는다.
start, end = map(int, sys.stdin.readline().split())


# 최소 비용을 찾는 함수다.
def DIJKSTRA(start):
    # queue를 하나 만들고, 힙으로 비용과 출발 도시를 넣어준다.
    queue = []
    heapq.heappush(queue, (0, start))

    while queue:
        # 0, start -> 아래 과정을 통해 queue는 새로운 비용, start와 연결된 어느 정점으로 갱신된다.
        fee, now = heapq.heappop(queue)

        # 기존 최단 거리 비용이 더 낮다면 갱신해줄 필요가 없다.
        if cost_table[now] < fee:
            continue

        # 현재 정점과 연결된 모든 정점들을 확인한다.    
        for adj_now in graph[now]:
            # 현재 정점과 인접한 정점의 비용(adj_now[1])과 현재 정점의 비용을 더해서 새로운 비용을 구한다.
            new_fee = fee + adj_now[1]
            # 새로운 비용이 cost_table내의 인접 정점 비용보다 작다면
            if new_fee < cost_table[adj_now[0]] :
                # cost_table내의 인접 정점 비용을 새로운 비용으로 갱신한다.
                cost_table[adj_now[0]] = new_fee
                # 그리고 새로운 비용과 인접 정점을 힙에 넣어준다.
                heapq.heappush(queue, (new_fee, adj_now[0]))

DIJKSTRA(start)
if cost_table[end] != int(1e9):
    print(cost_table[end])
else :
    print(-1)

 

▶ 관련 링크

2021.11.18 - [알고리즘] - DFS(Depth First Search, 깊이 우선 탐색)이란?

2021.11.18 - [알고리즘] - BFS(Breadth First Search, 너비 우선 검색)이란?

2021.11.19 - [알고리즘] - 그래프(Graph)란?

2021.11.19 - [알고리즘] - DFS & BFS : DFS와 BFS(백준 1260번)

2021.11.19 - [알고리즘] - DFS & BFS : 연결 요소의 개수(백준 11724번)

2021.11.19 - [알고리즘] - DFS & BFS : 바이러스(백준 2606번)

2021.11.19 - [알고리즘] - DFS & BFS : 미로 탐색(백준 2178번)

2021.11.19 - [알고리즘] - DFS & BFS : 특정 거리의 도시 찾기(백준 18352번)

2021.11.19 - [알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)이란?