소스 코드

import sys
from collections import deque
input = sys.stdin.readline

# 무게 cost_of_object 만큼의 물건을 목표 섬까지 이동시킬 수 있는지 BFS로 판별
def deliver_object(cost_of_object, START, END, N):
    dq = deque([START])
    visited = [False] * (N + 1)
    visited[START] = True

    while dq:
        cur_v = dq.popleft()

        for adj_v, cost in edges[cur_v]:
            if cost_of_object <= cost and not visited[adj_v]:
                visited[adj_v] = True
                dq.append(adj_v)
    
    return visited[END]

N, M = map(int, input().rstrip().split())
edges = [[] for _ in range(N + 1)]

for _ in range(M):
    A, B, C = map(int, input().rstrip().split())
    edges[A].append((B, C))
    edges[B].append((A, C))

START, END = map(int, input().rstrip().split())

left_cost = 1
right_cost = 1000000000

# 옮길 물건의 가능한 무게의 최대치를 이분 탐색
while left_cost <= right_cost:
    mid_cost = (left_cost + right_cost) // 2

    if deliver_object(mid_cost, START, END, N):
        left_cost = mid_cost + 1
    else:
        right_cost = mid_cost - 1

print(right_cost)

풀이 요약

1. 정답 값인 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 찾기 위해, 한 번의 이동에서 옮길 수 있는 물품들의 중량을 대상으로 이분 탐색한다.

2. 각 탐색 단계의 중량 값에서, 해당 중량 값을 갖는 물건을 목표 섬까지 옮기는 것이 가능한지를 판단하기 위해 BFS를 수행한다.

3. BFS를 수행할 때, 인접 노드로 진행할 때 해당 엣지의 가중치가 이분 탐색의 현재 단계 중량 값 보다 작으면, 중량 초과이므로 이 경우는 패싱해주는 식으로 구현하면 된다.

어려웠던 점, 배운 점

• 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며 라는 문제의 조건을 보고, 어떻게 중량제한이 큰 엣지 하나만 남겨두고 다른 중복되는 엣지(다리)는 제거할 수 있을까. 를 한참을 고민했는데 잘 안돼서 다른 사람 풀이를 참고했다. 결론은 그럴 필요 없이 그냥 엣지 다 저장하고, 같은 두 섬을 잇는 다리가 여러 개 있으면 그냥 그 엣지들도 다른 엣지들과 똑같이 전부 순회해줘도 아무 문제 없는 것이었다...

• 다른 사람 풀이를 보고 엣지 저장 고민을 해결했고, 그 후 백트래킹으로 풀어봤지만 TLE가 떴다. 다시 다른 사람 풀이를 참고했고, 이분 탐색 및 BFS 아이디어로 풀 수 있었다. 풀고 나니 참 간단한 문제인데, 아직 사고력이 부족한가보다..ㅠ