[Baekjoon Online Judge] 백준 1939번 중량제한(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1939번 중량제한

(Python)

(글쓴날 : 2020.04.07)

 

---

* Baekjoon Online Judge, 백준 1939번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1939번 중량제한

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1939

1939번: 중량제한

---

2) 풀이 과정

N개의 섬과 M개의 다리가 주어지고, 각 다리의 연결된 섬과 중량 정보가 주어질 때, 공장이 위치한 섬끼리 한 번의 이동에서 옮길 수 있는 물품들의 최대 중량을 구하는 문제입니다.

 

저의 경우, 이분 탐색과 BFS를 적용하여 문제에 접근하였고, 각 다리의 정보를 인접 리스트로 저장한 뒤 최대 중량을 중간값으로 설정하여 이분 탐색하는 동시에 너비 우선 탐색을 실시하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
bridges = [list(map(int, input().split())) for _ in range(M)]
factory = list(map(int, input().split()))
result = 0
 
adjacentList = [[] for _ in range(N + 1)]
 
for bridge in bridges:
    adjacentList[bridge[0]].append((bridge[1], bridge[2]))
    adjacentList[bridge[1]].append((bridge[0], bridge[2]))
 
 
def BFS(vertex, mid):
    visit = [False] * (N + 1)
    dq = deque()
 
    dq.append(vertex)
 
    while len(dq):
        vertex = dq.popleft()
 
        if not visit[vertex]:
            visit[vertex] = True
            
            if vertex == factory[1]:
                return True
 
            for edge in adjacentList[vertex]:
                if edge[1] >= mid:
                    dq.append(edge[0])
 
    return False
 
 
left = 0
right = 1000000000
 
while left <= right:
    mid = (left + right) // 2
 
    if BFS(factory[0], mid):
        result = mid
        left = mid + 1
    else:
        right = mid - 1
 
print(result)

---