문제

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

소스코드

import sys
sys.stdin = open("input.txt", 'r')
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

if __name__ == "__main__": 
    n,m = map(int,input().split())
    adjust_list = [[] for _ in range(n+1)]
    for _ in range(m):
        s,e,v = map(int,input().split())
        adjust_list[s].append([e,v])
        adjust_list[e].append([s,v])
    v1,v2 = map(int,input().split())

    def bfs(c):
        q = deque()
        q.append(v1)
        visited = [False] * (n+1)
        visited[v1] = True

        while q:
            cur = q.popleft()
            if cur == v2:
                return True
            for e,w in adjust_list[cur]:
                if not visited[e] and w >= c:
                    visited[e] = True
                    q.append(e)

        return False

    def dfs(start,c):
        if start == v2:
            return True
        for y,w in adjust_list[start]:
            if not visited[y] and w >= c:
                visited[y] = True
                if dfs(y,c):
                    return True 
        return False

    
    l,r = 1,1000000000 #l값을 0으로 해서 탐색하면 메모리 초과
    ans = 0
    while l <= r:
        visited = [False] * (n+1)
        visited[v1] = True
        mid = (l+r)//2
        if dfs(v1,mid):
            l = mid + 1
            ans = mid
        else:
            r = mid -1
    print(ans)

설명

1. bfs나 dfs를 이용해서 시작섬에서 끝섬으로 갈 수 있는지 체크한다.
2. 경로 탐색하면서 중량의 최대 값을 체크한다 -> 이분 탐색으로 탐색

bfs 이용해서 섬 탐색 시 입력을 받을 때 인접리스트를 사용해서 받아준다.
양방향이므로 둘 다의 인접리스트를 생성해준다.
queue를 이용해서 bfs 탐색 (이때 이분 탐색하여 얻은 mid 값이 섬의 중량을 초과하는지 체크해서 최대 중량을 찾는다.)

후기

탐색은 했는데 중량을 구할 때 이분 탐색을 안하니까 메모리 초과가 발생