[알고리즘 문제 풀이][파이썬] 백준 1939번: 중량제한

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

📑 문제 설명
1. N개의 섬이 있고 섬은 다리로 이어져 있다.
2. 다리마다 중량제한이 있다.
3. 이 때 한번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하라.

입력: 첫째 줄에 섬의 개수 N과 edge의 개수 M이 주어진다. 둘째 줄부터 M+1째 줄까지 A, B, C가 주어지며 A와 B를 잇는 다리가 존재하고 그 다리의 중량제한은 C이다를 의미한다.
마지막 줄에 우리가 구하고자 하는 두 섬을 입력한다.(마지막 줄에 있는 두 섬을 잇는 최대중량 구하기)
출력: 최대중량

💡 문제 해결 방법
알고리즘: BFS + 이분 탐색

알고리즘 선택 이유
1. 이어진 모든 노드를 방문
2. edge의 중량만 비교하며 방문하면 됨

예외처리 및 추가 내용
1. dfs + 백트래킹으로 1차 시도

• n이 10000까지 가능하기 때문에 재귀함수 호출 시 터짐
• bfs + 이분탐색 조합으로 풀어야 함

2. bfs + 이분 탐색
3. 중량제한을 low = 0, high = (입력받은 다리 중 가장 무거운 중량) 으로 초기화
4. mid = (low + high) // 2로 설정
5. 시작 지점으로부터 bfs를 진행하다가
   • 중량(mid)을 이길 수 있는 다리가 없다면 이동 불가 --> high = mid - 1
   • 중량(mid)을 이길 수 있는 다리가 있다면 도착 가능 --> low = mid + 1

스터디 내용
1. 일반 그래프 문제
2. undirected graph
3. find all paths 문제
- dfs + 백트래킹 --> n의 개수를 체크해야 함 여기서는 10000으로 크기 때문에 dfs 불가
4. minimum은 길 중에서 가장 작은 weight, 여러 개의 길을 찾았다면 그 중에서 가장 maximum weight를 선택
5. multiple graph에 가장 최초의 그래프: seven bridges problem
- multiple graph는 weight vs unweight 그래프에 따라 달라짐
- edge list로 저장하는 것이 비교적 현명
- 하지만 이 문제는 일단 weight 그래프이므로 입력은 그대로 받아도 됨

💻 코드

import sys
from collections import deque

def bfs(s, e, visit, mid):
    queue = deque([s])
    while(queue):
        node = queue.popleft()
        print(node)
        if node == e:
            return mid + 1
        for i in graph[node]:
            b = i[0]
            c = i[1]
            if c >= mid and visit[b] == False:
                queue.append(b)
                visit[b] = True
    return mid - 1

def binary_search(low, high):
    while (low <= high):
        visit = [False for x in range(n+1)]
        mid = (low + high)//2
        newmid = bfs(s, e, visit, mid)
        if newmid == mid - 1:
            high = newmid
        elif newmid == mid + 1:
            low = newmid
    print(high)



n, m = map(int, sys.stdin.readline().split())
graph=[[-1]]+[[]for x in range(n+1)]
low = 0
high = 0
for i in range(m):
    a, b, c= map(int, sys.stdin.readline().split())
    graph[a].append([b, c])
    graph[b].append([a, c])
    high = max(high, c)
s, e = map(int, sys.stdin.readline().split())

binary_search(low, high)

💟 추가적으로 알게 된 점
1. 이분 탐색(binary search)
2. 이 문제는 모든 길을 탐색해서 최대의 중량을 찾으라는 문제가 아님 --> 모든 길 찾기는 dfs + 백트래킹의 조합인데 그러기에는 n(노드 수)이 너무 커서 프로그램이 터짐
3. 모든 길 찾기가 아닌, 이 중량을 선택했을 때 start node 부터 end noed 까지 갈 수 있어? 없으면 중량을 줄여보고 가능하면 중량을 더 키워보자 관점에서 접근해야 함
- 이렇게 중량을 설정하고 길을 탐색하면 자연스럽게 두 노드를 잇는 edge가 2개 이상 존재하더라도 중량 if 문에 걸려서 최적의 길만 선택이 가능함