백준 1939 중량제한 파이썬 풀이

난이도 : 골드3

풀이일 : 2404022

https://www.acmicpc.net/problem/1939

1939번: 중량제한

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys, heapq

N, M = map(int, sys.stdin.readline().split())
loads = [[] for _ in range(N + 1)]  # 다리 연결 및 중량제한

for _ in range(M):  # 최대힙으로 사용하기 위해 -C 형태로 저장
    A, B, C = map(int, sys.stdin.readline().split())
    loads[A].append([-C, B])
    loads[B].append([-C, A])

S, E = map(int, sys.stdin.readline().split())
maxi = [0] * (N + 1)  # 출발지에서 각 섬까지의 최대 중량

queue = []
heapq.heappush(queue, [-10 ** 9, S])  # 최대치로 초기 설정
while queue:
    cost, x = heapq.heappop(queue)
    # 목적지에 도착했다면 중단
    if x == E:
        break
    # 현재 무게보다 더 큰 중량제한이 저장되어 있다면 무시
    if maxi[x] < cost:
        continue
    # 연결된 섬까지 중량제한, 섬 번호 저장
    for temp, nx in loads[x]:
        # cost, temp 중 작은 중량제한 선택
        select = max(cost, temp)
        # 저장된 무게보다 큰 중량제한일 경우 maxi 재할당
        if maxi[nx] > select:
            maxi[nx] = select
            heapq.heappush(queue, [select, nx])

print(-maxi[E])

• loads : 각 섬과 연결된 섬까지의 중량제한, 각 섬의 번호를 저장할 배열
• loads[A].append([-C, B]) : 최대힙을 사용하기 위해 중량제한 수치를 -C 형태로 저장
• maxi : 출발지에서 각 섬까지 최대 중량제한을 저장할 배열
• cost : 현재 섬 x에서의 중량제한
• x가 도착지 E와 같다면 중단 (이 조건만 삭제해도 통과)
• 현재 무게보다 더 큰 중량제한이 저장되어 있다면 무시하고 통과 (이 조건만 삭제해도 통과)
• 위 두 줄에 해당하는 코드는 한 개 지워도 통과처리가 되지만, 둘 다 지우면 성능이 크게 떨어져 시간초과로 오답처리가 됩니다.
• 현재 섬 x와 연결된 섬들 nx에 대해 중량제한 temp와 현재 중량제한 cost를 비교하여 select에 할당
• 만약 현재 저장된 해당 섬까지의 중량제한이 select보다 작다면, 중량제한을 select로 재할당하고 해당 정보 queue에 추가

---

느낀점

• 처음에는 아무 생각없이 중량들을 더해 다익스트라처럼 풀다가 틀렸다. 문제가 하는 말을 제대로 알아듣고 코드를 짜자.
• 최대 중량제한을 저장하지만, 여러 섬을 돌아 도착하는 경로는, 지나온 경로 중 가장 작은 중량제한 값을 가진다는 게 헷갈려서 틀렸었다. 별 거 아닌 것 같은데 헷갈려서 한 시간이나 고민하며 고쳐 푼 문제.
• if x == E: break 문과 if maxi[x] < cost: continue 문 둘 중 한 가지는 지워도 괜찮지만, 둘 다 지워버리면 시간초과로 틀린다는 점이 재미있었다. 첫 번째 조건은 목적지에 도착한 이후 다른 노드로의 불필요한 방문을 막는 역할을 하고, 두 번째 조건은 이미 더 높은 중량제한으로 목적지에 도착할 수 있다면 탐색을 중단시키는 역할을 하는데, 두 번째 조건을 삭제하는 경우와 두 조건이 모두 있는 경우는 백준 채점상 시간차이가 별로 안 나지만(심지어 삭제한 시간이 조금 더 빠르지만), 첫 번째 조건을 삭제하는 경우는 시간차이가 꽤 난다. 조금 더 살펴봐야지