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

출력

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

예제 입력 1 

5

8

1 2 2

1 3 3

1 4 1

1 5 10

2 4 2

3 4 1

3 5 1

4 5 3

1 5

예제 출력 1 

4

 

 

👩‍🦰 나의 풀이

import sys
import heapq
from collections import defaultdict
input=sys.stdin.readline

N=int(input())      # 도시의 개수
M=int(input())      # 버스의 개수
bus=[list(map(int, input().split())) for _ in range(M)]     # 출발 도시, 도착 도시, 비용
start, end=map(int, input().split())        # 출발 도시, 도착 도시
dic=defaultdict(list)

for s, e, v in bus :
    dic[s].append((v, e))		# 출발도시 : (비용, 도착도시)

que=[(0, start)]
visited=[float('inf')] * (N+1)
visited[start]=0

while que :
    value, num=heapq.heappop(que)      # 비용이 낮은 순으로 pop
    if visited[num] < value :	# 비용이 높아서 도시 num에 방문하지 않음
        continue
    for v, n in dic[num] :	 # num과 연결된 도시들 탐색
        if visited[n] > value + v :		# 도시 n의 비용을 갱신
            visited[n]=value + v	# 도시 num에서 도시 n에 방문
            heapq.heappush(que, (value + v, n))

print(visited[end])

if visited[num] < vlaue : continue로 추가하니 통과

이전까지의 num 도시 비용보다 비용 value가 더 크면 방문할 필요없다.

 

 

# 시간초과
import sys, heapq
input=sys.stdin.readline

N=int(input().rstrip())     # 도시
M=int(input().rstrip())     # 버스
bus=[[] for _ in range(N+1)]
visited=[float('inf')]*(N+1)

for m in range(M) :
    a, b, w=map(int, input().split())	# 출발 도시, 도착 도시, 비용
    bus[a].append([w, b])

start, end=map(int, input().split())	# 출발 도시와 도착 도시
que=[[0, start]]
visited[start]=0		# dp

while que :
    city=heapq.heappop(que)
    for c in bus[city[1]] :     # city[1]과 연결된 도시 탐색
        if visited[c[1]] > city[0]+c[0] :   # 비용 갱신
            visited[c[1]]=city[0]+c[0]
            heapq.heappush(que, [city[0]+c[0], c[1]])

print(visited[end])

 

시작 정점에서부터 다른 정점들까지의 최단 거리를 구하는 다익스트라 알고리즘 사용

다익스트라는 연결된 도시들을 모두 따져본다.

dp를 이용해서 start부터 end까지 비용을 구해간다. 

우선순위 큐 사용

문제에서 주어진 입력이 단방향인 것을 유의한다.

heap에서 비용이 작은 순서대로 뽑아야해서 비용을 0인덱스 위치에 둠

heap에서 뽑은 도시와 연결된 도시들을 for문으로 탐색한다.

연결된 도시의 비용 visited[c[1]]이 현재 도시 비용 city[0]+현재 도시와 연결된 도시 비용 c[0]보다 크면 갱신

que에 연결된 도시를 추가한다.

city=heapq.heappop(que)대신 city, city_v 이런 식으로 값 두개를 받았으면 가독성이 좋았을거다

 

 

# 시간초과
import sys
from collections import deque
from collections import defaultdict
from copy import deepcopy
input=sys.stdin.readline

N=int(input())      # 도시의 개수
M=int(input())      # 버스의 개수
bus=[list(map(int, input().split())) for _ in range(M)]     # 출발 도시, 도착 도시, 비용
start, end=map(int, input().split())        # 출발 도시, 도착 도시
dic=defaultdict(list)
for s, e, v in bus :
    dic[s].append((v, e))

def bfs(start, end) :
    answer=float("inf")
    visited=[0] * (N+1)
    visited[start]=1
    que=deque()

    for v, e in dic[start] :
        copied=deepcopy(visited)
        que.append((v, e, copied, 0))

    while que :
        value, num, visit, total_v=que.popleft()
        answer += value
        if num == end :
            answer=min(answer, total_v)
        visit[num]=1
        for v, e in dic[num] :
            if not visit[e] :
                copied=deepcopy(visit)
                que.append((v, e, copied, total_v + v))


    return answer

print(bfs(start, end))

모든 경우를 다 구하려니까 시간 초과..

도착하면 answer을 최소값으로 갱신

que에 비용, 도착 도시 번호, 방문 배열, 총 비용을 담았다.

 

 

# 실패
import sys
import heapq
from collections import defaultdict
input=sys.stdin.readline

N=int(input())      # 도시의 개수
M=int(input())      # 버스의 개수
bus=[list(map(int, input().split())) for _ in range(M)]     # 출발 도시, 도착 도시, 비용
start, end=map(int, input().split())        # 출발 도시, 도착 도시
dic=defaultdict(list)
for s, e, v in bus :
    dic[s].append((v, e))

def bfs(start, end) :
    answer=0
    visited=[0] * (N+1)
    heap=[(0, start)]
    while heap :
        value, num=heapq.heappop(heap)
        answer += value
        if num == end :
            break
        visited[num]=1
        for _ in dic[num] :
            heapq.heapify(dic[num])
            v, e=heapq.heappop(dic[num])
            if not visited[e] :
                heapq.heappush(heap, (v, e))
                break

    return answer

print(bfs(start, end))

어떤 노드에서 다른 노드로 갈때 그 순간에 가장 비용이 적은 노드를 고른다.

최선의 방법은 아님.

 

 

# 실패
import sys, heapq
from collections import deque
input=sys.stdin.readline

N=int(input())  # 도시
M=int(input())  # 버스
bus=[list(map(int, input().split())) for m in range(M)] # 버스 정보(출발, 도착, 비용)
start, end=map(int, input().split())    # 출발점, 도착점
info=[[] for i in range(N+1)]
visited=[0]*(N+1)
cost=0

for i in bus :
    info[i[0]].append((i[1], i[2]))     # (도착, 비용)
    #info[i[1]].append((i[0], i[2]))

def bfs():
    que=deque([(start, cost)])
    ans=0
    while que :
        city, money=que.popleft()
        ans+=money
        #if city == end:
         #   return ans
        if not visited[city] :      # 방문한 적 없음
            visited[city]=1
            for c in info[city] :
                if not visited[c[0]] :
                    if c[0] == end :
                        return c[1]+ans
                    que.append(c)
        que=deque(sorted(que, key=lambda x:x[1]))

                #if not visited[c[0]] :
                    #que.append(c)
            #for i in info[city] :       # 도착
             #   if i[0] == end :
              #      return i[1]+ans

            #small=heapq.nsmallest(1, info[city], key=lambda x:x[1])     # 비용이 가장 작은
            #que.extend(small)
            #ans+=small[1]

print(bfs())

이 문제를 bfs로 구현하기엔 부족함,,

 

 

👧 다른 사람 풀이

# https://pacific-ocean.tistory.com/283
import sys
from heapq import heappush, heappop
input=sys.stdin.readline
n=int(input())	# 도시
m=int(input())	# 버스
inf=100000000
s=[[] for i in range(n+1)]  	# 인덱스=출발, 값=[도착, 비용]
dp=[inf for i in range(n+1)]	# 도시별 비용
for i in range(m) :
    a, b, w=map(int, input().split())	# 출발, 도착, 비용
    s[a].append([b, w])
start, end=map(int, input().split())	# 출발점, 도착점
def dijkstra(start) :
    dp[start]=0
    heap=[]
    heappush(heap, [0, start])	# 비용, 도시
    while heap :
        w, n=heappop(heap)	# 비용, 도시
        if dp[n] < w :
            continue
        for n_n, wei in s[n] :	# 도시, 비용
            n_w=w+wei
            if dp[n_n] > n_w :
                dp[n_n]=n_w		# 더 작은 비용으로 갱신
                heappush(heap, [n_w, n_n])
dijkstra(start)
print(dp[end])

 

dp와 다익스트라 알고리즘 사용

단방향으로 인덱스=출발도시, 값=[도착도시, 비용]인 리스트 s를 생성

heap으로 쉽게 작은 비용을 가진 도시를 꺼낼 수 있다.

heap에서 뽑은 비용 w가 dp[n]보다 크면 건너띈다.

for문으로 n과 연결된 도시들 중 가장 비용이 작은 도시를 heap에 추가한다.

 

 

# https://jjangsungwon.tistory.com/28
import sys
from heapq import heappush, heappop

def dijkstra(start, end) :
    heap=[]
    heappush(heap, (0, start))      # 시작지점 힙에 추가
    distance=[sys.maxsize]*(N+1)    # 각 정점사이의 거리 무한대로 초기화
    distance[start]=0           # 시작 지점 0으로 초기화

    while heap :
        weight, index=heappop(heap)
        for e, c in bus[index] :
            if distance[e] > weight+c :
                distance[e]=weight+c
                heappush(heap, (weight+c, e))
    return distance[end]

if __name__ == "__main__" :
    # input
    N=int(input())  # 도시의 개수
    M=int(input())  # 버스의 개수
    bus=[[] for _ in range(N+1)]
    for _ in range(M) :
        start, end, cost=map(int, input().split())  # 출발지, 도착지, 비용
        bus[start].append((end, cost))
    start, end=map(int, input().split())    # 찾고자하는 비용 경로(출발지, 도착지)

    print(dijkstra(start, end))

 

위랑 같은 알고리즘

 

 

 

문제 출처 👉 백준