728x90
반응형
※ 문제링크
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스
www.acmicpc.net
해당 문제는 가중치가 있는 최단거리경로를 구하는 것과 관련된 문제로 가중치에 음수가 없으므로 다익스트라 알고리즘을 활용하여 해결할 수 있는 문제였다. 다만 경유하는 도시들의 숫자와 도시들을 같이 출력해줘야하는 것이 문제조건이기에 해당 부분만 추가하면 생각보다 쉽게 해결할 수 있는 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다.
1. 입력받은 값들을 바탕으로 리스트를 활용하여 그래프를 구현해준다.
2. heapq와 동적프로그래밍 개념을 사용하여 최단거리를 구할 다익스트라 알고리즘의 토대를 쌓고, 가중치, 도착도시, 경유도시목록을 기록 및 갱신할 수 있게 약간 변형하여 함수를 작성한다.
3. 반복문이 종료되면 도착도시의 최단경로, 경유한 도시의 수, 경유한 도시목록을 출력해준다.
+ 시간 단축을 위해 sys를 사용해주었다.
from heapq import heappush, heappop
import sys
# input = sys.stdin.readline
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
s, e, c = map(int, input().split())
graph[s].append([c, e])
start, end = map(int, input().split())
def dijkstra(start, end):
heap = []
dp = [float('inf') for _ in range(n+1)]
cities = [[] for _ in range(n+1)]
dp[start] = 0
cities[start] = [start]
heappush(heap, [0, start, [start]])
while heap:
cost1, cp1, city = heappop(heap)
if dp[cp1] < cost1: # 해당부분이 빠지면 시간초과가 뜨니 유의해주세요.
continue
for cost2, cp2 in graph[cp1]:
cost_n = cost1 + cost2
if cost_n < dp[cp2]:
dp[cp2] = cost_n
cities[cp2] = city + [cp2]
heappush(heap, [cost_n, cp2, city + [cp2]])
print(dp[end])
print(len(cities[end]))
print(*cities[end])
return
dijkstra(start, end)
P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 5014번 스타트링크 / 사용언어 : 파이썬(python) (0) | 2022.02.14 |
---|---|
[BOJ] 1715번 카드 정렬하기 / 사용언어 : 파이썬(python) (0) | 2022.02.13 |
[BOJ] 2075번 N번째 큰 수 / 사용언어 : 파이썬(python) (0) | 2022.02.10 |
[BOJ] 1238번 파티 / 사용언어 : 파이썬(python) (0) | 2022.02.09 |
[BOJ] 2644번 촌수계산 / 사용언어 : 파이썬(python) (0) | 2022.02.08 |
댓글