[Python] 1939. 중량제한

문제

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

1939번: 중량제한

 

---

풀이 과정

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구해야 하므로, 공장 두 곳을 이은 다리들 중 중량 제한이 더 큰 다리를 건너는 것이 좋다.

따라서 입력받은 다리 정보들을 다리의 중량 제한을 기준으로 하여 내림차순으로 정렬하고,
다익스트라를 사용하되 힙에 push 할 때, 중량을 마이너스를 붙여 push 하여 최대 힙으로 사용하였다. 

1. 입력받은 다리 정보들을 중량 제한을 기준으로 하여 내림차순 정렬한다.
2. 다익스트라 함수로 들어가 중량의 최솟값(-999999999)과 시작 공장(factory1)을 queue에 넣어주고,
   끝 공장(factory2)를 만날 때까지 while문을 돌며 아래의 과정(3 ~ 7)을 반복한다. 
3. queue에서 최대 중량(w)과 섬(now)을 가져오고, 중량 값을 원상 복구시킨다.
4. 현재 섬에서 갈 수 있는 다리를 탐색한다. 
5. 현재 중량(w)과 다음 섬의 최대 중량(nw) 중, 더 작은 중량을 nw 변수에 저장한다. 
   (중량을 더 작은 것으로 갱신해야 함. 큰 중량으로 갱신하면 해당 섬(nxt)을 지나가지 못한다.)
6. nw의 중량이 저장되어 있는 기존의 중량(dist[nxt])보다 큰 경우, 해당 중량으로 갱신시키고 큐에 넣어준다.
   (해당 섬에서 탐색하기 위함. 이때 최대 힙이므로 중량에 -를 붙여 넣어준다.)
7. queue에서 꺼낸 다리의 최대 중량이 저장되어 있는 다리의 최대 중량보다 작을 경우, continue 해준다.
   왜냐하면 더 큰 중량으로 지나갈 수 있는 다리가 있기 때문에 해당 다리는 탐색하지 않아도 되기 때문이다. 
8. 중간에 공장 2에 도착하게 되면 현재 중량(최대 중량)을 return 해준다.

 

위의 풀이 과정으로 해결하고 다른 분들의 풀이를 보았는데, 보통 BFS + 이분 탐색을 많이 사용하여 푸셔서 해당 방법으로도 해결해보았다.

1. 입력받은 다리 정보들을 중량 제한을 기준으로 하여 내림차순 정렬한다.
2. 최소 중량(low)을 1, 최대 중량(high)을 1000000000으로 잡는다. 
3. 최소 중량이 최대 중량의 값과 같아지거나 커질 때까지 아래 과정을 반복한다.
   1. 최소 중량과 최대 중량의 중간 중량(mid)을 구한다.
   2. 해당 중량으로 bfs 함수를 실행한다.
      2-1) 공장 1에서부터 갈 수 있는 섬 중, 방문하지 않았고 전달받은 중량(weight)으로 갈 수 있다면
      queue에 넣는다.
      2-2) queue에서 뽑은 섬이 공장 2의 위치라면 True를 반환한다.
      2-3) queue가 빌 때까지 위 과정을 반복해도 공장 2에 도달하지 못했다면 False를 반환한다.
   3. bfs 함수에서 True를 반환받았다면 최소 중량을 중간값 + 1의 값으로 잡아 중량을 높여보고,
      False를 반환받았다면 최대 중량을 중간 중량 -1의 값으로 잡아 중량을 낮춘다.
4. 최댓값을 반환해야 하므로 최대 중량에 담긴 값을 print 한다. 

 

---

코드

1. Dijkstra를 활용한 풀이

import heapq

def dijkstra():
    dist = [0 for _ in range(n + 1)]
    dist[factory1] = 999999999999

    queue = []
    heapq.heappush(queue, [-999999999999, factory1])

    while queue:
        w, now = heapq.heappop(queue)
        w *= -1

        if now == factory2:
            return w

        if dist[now] > w:
            continue

        for nxt, nw in bridge_info[now]:
            nw = min(w, nw)

            if dist[nxt] < nw:
                dist[nxt] = nw
                heapq.heappush(queue, [-nw, nxt])


n, m = map(int, input().split())
bridge_info = [[] for _ in range(n+1)]
for _ in range(m):
    bridge1, bridge2, weight = map(int, input().split())
    bridge_info[bridge1].append([bridge2, weight])
    bridge_info[bridge2].append([bridge1, weight])

factory1, factory2 = map(int, input().split())

for i in range(1, n+1):
    bridge_info[i].sort(key = lambda x: -x[1])

print(dijkstra())

 

2. BFS + 이분 탐색을 활용한 풀이

from collections import deque

def bfs(weight):
    visited = [0 for _ in range(n + 1)]
    visited[factory1] = True

    queue = deque([factory1])
    while queue:
        now = queue.popleft()

        if now == factory2:
            return True

        for nxt, nxt_w in bridge_info[now]:
            if not visited[nxt] and weight <= nxt_w:
                visited[nxt] = True
                queue.append(nxt)

    return False


n, m = map(int, input().split())
bridge_info = [[] for _ in range(n+1)]
for _ in range(m):
    bridge1, bridge2, weight = map(int, input().split())
    bridge_info[bridge1].append([bridge2, weight])
    bridge_info[bridge2].append([bridge1, weight])

factory1, factory2 = map(int, input().split())

for i in range(1, n+1):
    bridge_info[i].sort(key = lambda x: -x[1])

low, high = 1, 1000000000
while low <= high:
    mid = (low + high) // 2
    if bfs(mid):
        low = mid + 1
    else:
        high = mid - 1

print(high)