문제 링크

중량제한

문제 설명

N개의 섬으로 이루어진 나라가 있는데, 몇개의 섬들은 다리로 이어져 있다. 두 섬에 공장을 세우고 서로 물품을 수송할 때, 다리마다의 중량제한을 초과하지 않고, 한번의 이동에서 옮길 수 있는 최대 중량은?

문제 풀이

1. 각 섬마다의 다리를 양방향 그래프로 저장한다.

#양방향 그래프로 저장하기
for _ in range(M):
    island_A, island_B, weight = map(int, input().split())
    islands[island_A].append([island_B, weight])
    islands[island_B].append([island_A, weight])
departure, destination = map(int, input().split())

2. 이분탐색의 대상을 옮길 수 있는 최대 중량으로 두고, 이분탐색을 한다.
   해당 무게로 운반이 가능하면 무게를 늘리고, 운반이 불가능하면 무게를 줄인다.

#이분탐색 -> 대상 : 무게
min_val, max_val = 1, 1000000000
while min_val <= max_val:
    visit = [0 for _ in range(N+1)]
    mid = (min_val+max_val)//2
    #해당 무게로 이동 가능하면 무게 늘리기
    if bfs(mid):
        min_val = mid + 1
    else:
        max_val = mid - 1

3. 운반이 가능함은 bfs로 찾는다. 시작 섬과 다리로 연결된 섬 중, 아직 방문하지 않고, 운반가능한 무게가 운반하려는 무게보다 크거나 같은 섬을 큐에 넣고 탐색한다.

def bfs(mid):
    queue = deque([departure])
    visit[departure] = 1

    while queue:
        start = queue.popleft()
        if start == destination:
            return True
        for island_B, weight in islands[start]:
            if visit[island_B] == 0 and mid <= weight:
                queue.append(island_B)
                visit[island_B] = 1
    return False

전체 코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
islands = [[]*(N+1) for _ in range(N+1)]

#양방향 그래프로 저장하기
for _ in range(M):
    island_A, island_B, weight = map(int, input().split())
    islands[island_A].append([island_B, weight])
    islands[island_B].append([island_A, weight])
departure, destination = map(int, input().split())

def bfs(mid):
    queue = deque([departure])
    visit[departure] = 1

    while queue:
        start = queue.popleft()
        if start == destination:
            return True
        for island_B, weight in islands[start]:
            if visit[island_B] == 0 and mid <= weight:
                queue.append(island_B)
                visit[island_B] = 1
    return False

#이분탐색 -> 대상 : 무게
min_val, max_val = 1, 1000000000
while min_val <= max_val:
    visit = [0 for _ in range(N+1)]
    mid = (min_val+max_val)//2
    #해당 무게로 이동 가능하면 무게 늘리기
    if bfs(mid):
        min_val = mid + 1
    else:
        max_val = mid - 1
print(max_val)

느낀점

두가지 알고리즘을 이용해서 푸는 문제는 처음 풀어봐서 생각해내는게 어려웠다,, bfs와 이분탐색 둘다 활용해야 하는 좋은 문제인 것같다. 비슷한 문제 많이 풀어보면 좋을듯,, 이분탐색은 탐색할 대상 찾는게 넘 어려웡