[백준 1939] 중량제한 (python 풀이)

1. 문제 

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.진다.

3. 출력

첫째 줄에 답을 출력한다

---

4. 포인트

1. 그래프 탐색의 개념과 구현을 잘 기억해 놓자
2.  시간의 최소화를 위해서 리스트 사용 대신 단순히 값으로 조작하거나 set 을 사용해 해결할 수 있는지 검토해보자
3. dictionary 생성시 DefaultDict 보단 dic = [[] for i in range(N+1)] 과 같은 표현을 이용하자

4. 문제 풀이

 전형적인 그래프 탐색문제 였다. 거기에 추가로 값의 범위가 10억으로 매우 크게 주어져 그래프 탐색에 이진탐색을 사용해 풀 수 있는 문제였다. 그래프 탐색 자료구조를 공부해보긴 했지만 문제로 접한게 처음이고 조금의 응용이 들어가서 다소 까다롭게 느꼈졌다. 

 게다가 BFS 와 이진 탐색을 통해 풀었음에도 자꾸만 시간초과를 마주했다. 값의 범위가 매우 큰경우 시간을 최소화하기 위해 set 을 활용하거나 단순히 메모리에서 값을 관리해서 품으로써 리스트 사용을 최소화 할 필요가 있다.

 

# 중량제한
from collections import deque

def BFS(mid : int):
    visited = set()
    need_visit = deque()

    visited.add(start_node)
    need_visit.append(start_node)


    while need_visit : 
        ele = need_visit.popleft()
        for i in dic[ele]:
            y , weight = i
            if weight >= mid and y not in visited:
                visited.add(y)
                need_visit.append(y)
    if end_node in visited:
        return True
    else:
        return False


N , M = map(int , input().split())

node_set = set()
dic = [[] for i in range(N+1)] 

min_val = 1000000000
max_val = 0
result = 0

for i in range(M):
    x, y , weight = map(int , input().split())
    node_set.add(x)
    dic[x].append((y,weight))
    dic[y].append((x , weight))

    min_val = min(min_val , weight)
    max_val = max(max_val , weight)

start_node , end_node =  map(int , input().split())
result = min_val


while min_val <= max_val :
    mid = (max_val + min_val)  //2
    if BFS : 
        result = mid
        min_val = mid+1
       
    else:
        max_val = mid -1

print(result)