1939(중량제한) - 파이썬

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

1939번: 중량제한

---

내 풀이

import sys
from collections import deque

input = sys.stdin.readline
    
def solution():
    n,m = map(int,input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        graph[a].append((b,c))
        graph[b].append((a,c))
    start,end = map(int,input().split())
    
    
    
    def bfs(k):
        q = deque([start])
        visit=[0]* (n+1)
        visit[start]=True
        
        while q:
            x = q.popleft()
            for i,j in graph[x]:
                if not visit[i] and j>=k:
                    visit[i]=1
                    q.append(i)
        return True if visit[end] else False
    
    def binary():
        answer=0
        left,right =0,int(1e9)
        
        while left<=right:
            mid = (left+right)//2
            if bfs(mid):
                answer = mid
                left = mid +1
            else:
                right = mid -1
        print(answer)
    binary()
solution()

---

개인적으로 좋은문제라고 생각했다!

bfs와 이진탐색의 결합이였는데 문제자체가 풀고나니 어렵지는 않았는데(전형적인 허세) 풀이과정을 생각해내기가 쉽지않아

구글링 좀 해보았다

 

---

다른사람의 풀이

 

 

---

https://velog.io/@ckstn0778/백준-1939번-중량제한-1-Python

백준 1939번 - 중량제한(★★★ / ▲▲ / 2) : Python

---