중량제한

문제분석

굉장히 많은 시행착오 끝에 다익스트라 알고리즘으로 풀었다. 1753_최단경로포스팅을 참고하며 겨우겨우 풀 수 있었다. 다익스트라에 대해 조금 더 깊게 이해할 수 있었던 문제였다.

시행착오

  • BFS접근
  • DFS접근
  • 다익스트라 알고리즘(목적지에 도착하면 while문을 탈출해야했는데, 끝까지 탐색해서 시간초과 발생)

테스트케이스

4 4
1 2 3
2 3 2
2 4 1
3 4 2
1 4
answer:2

6 9
1 2 3
2 4 4
4 5 4
5 6 4
6 1 4
1 3 5
3 6 1
3 5 3
3 4 2
1 5
answer:4

Crepe

내가 사용했던 테스트케이스에 대한 그림을 보며 다익스트라 알고리즘에 대해 이해해보자.

1과 5사이에 나를 수 있는 무게의 최대값을 구해야 한다. 출발지를 어디로 하든 상관은 없지만, 나는 1을 출발지로 선택했다.

먼저 1부터 해당 좌표까지 운반할 수 있는 무게의 최대값을 저장할 리스트 dp를 만들어준다. 초기값은 모두 0으로 세팅하고, 출발지의 dp값은 inf(2147000000)로 설정했다. 그 이유는 밑의 설명을 모두 읽으면 이해될 것이다.

1번 점에서 갈 수 있는 점은 2,3,6이다. 우리는 옮길 수 있는 무게의 최대값을 구하고 있음으로 dp에 기존에 저장되어있는 값과, 해당 값을 비교해 더 큰 수를 저장해준다. ex) dp[2]=max(0,3)

1번 점에서 갈 수 있는 점에 대해 탐색이 끝났으면, 아직 방문하지 않은 점들(1을 제외한 점들) 중 dp값이 가장 큰 점으로 이동해서 탐색한다. dp[3]이 5로 최대임으로 3번점으로 이동하자.

3번 점에서 갈 수 있는 아직 방문하지 않은 점은 4,5,6이다. 1번 점에서 했던 방식대로 똑같이 반복하면 되는데, 이때 주의할 점이 있다. 3번 점 까지 올 때 옮길 수 있는 화물의 최대값이 5임으로, 3번에서 뻗어나가는 점들에 대해서는 해당 점 까지 옮길 수 있는 화물의 최대값은 절대 5를 넘길 수 없다. ex) dp[6]=max(4,min(5,a)) 3과 6사이에 옮길 수 있는 화물의 무게가 a라면, a를 먼저 dp[3]=5와 비교해 둘중 더 작은 값을 dp[6]에 이미 저장되어있었던 4와 비교한다.

이렇게 모든 점들을 방문하면, 1부터 각 점들까지 옮길 수 있는 화물의 최대값이 dp에 저장된다.

1939_중량제한 문제에서는 모든 점들에 대해 알아야 할 필요는 없고, 서로 다른 두 섬 사이에 대해서만 알아내면 되기 때문에, 해당 점을 방문하는 순간 해당 점의 dp값을 출력하고 종료하면 된다.(이렇게 하지 않아 시간초과가 발생했다.) 다른 점들을 추가로 탐색하지 않아도 되는 이유는 조금만 생각해보면 쉽게 알 수 있다.

PLUS

1753_최단경로 여기서도 언급했듯이, 다익스트라 알고리즘을 사용할 때, 방문하지 않은 점들 중 옮길 수 있는 무게가 최대인 점을 우선적으로 탐색할 때 ‘최대or최소 힙’을 사용해야 시간복잡도를 줄일 수 있다. 이 문제에서는 최대힙을 사용했다.

CODE

import heapq
import sys
read = sys.stdin.readline
n, m = map(int, read().split())

bridge = list(dict() for _ in range(n+1))
for _ in range(m):
    a, b, c = map(int, read().split())
    if b in bridge[a]:
        bridge[a][b] = max(bridge[a][b], c)
    else:
        bridge[a][b] = c
    if a in bridge[b]:
        bridge[b][a] = max(bridge[b][a], c)
    else:
        bridge[b][a] = c

fac1, fac2 = map(int, read().split())

dp = list(0 for _ in range(n+1))
dp[fac1] = 2147000000
dp[0] = -1

save = []
heapq.heappush(save, [-2147000000, fac1]) #최대힙 사용

while save:
    w, p = heapq.heappop(save)
    if p == fac2:
        break
    w = -w
    for p_new in bridge[p]:
        w_new = bridge[p][p_new]
        if dp[p_new] < min(dp[p], w_new):
            dp[p_new] = min(dp[p], w_new)
            heapq.heappush(save, [-dp[p_new], p_new])
print(dp[fac2])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]