1939. 중량제한

문제링크

난이도	정답률(_%)
Gold IV	24.055%

메모리 (KB)	시간 (ms)
139596	560

설계

처음에 섬 사이의 다리 정보를 인접행렬 형태로 저장하려고 했다. 이렇게 하면 10000* 10000 만큼의 메모리가 사용되서 계속 메모리 초과를 일으켰다. 그래서 유효한 다리 정보만 저장할 수 있도록 인접리스트 형태로 저장했다.

이번에는 시간초과를 일으켰다. 처음 문제를 접근한 방식은 도착할 공장에서부터 거꾸로 시작점까지 bfs로 탐색해 최댓값을 구하는 것이었다. 이 방법은 모든 경로를 탐색하기 때문에 시간초과가 일어날 수 밖에 없었다.

이분탐색을 통해 물품의 중량을 미리 정해놓고 bfs를 통해 시작점에서 도착점으로 이동할 수 있는지 판단해서 중량의 범위를 좁혀나가는 방법으로 문제를 해결했다.

시간복잡도

O(1/log(max(w)) * (N + M))

코드

n, m = map(int, input().split())
islands = {}
maxW = 0
for i in range(m):
    r, c, w = map(int, input().split())
    islands.setdefault(r, {})
    if islands[r].get(c, 0) < w:
        islands[r][c] = w
    islands.setdefault(c, {})
    if islands[c].get(c, 0) < w:
        islands[c][r] = w
    if maxW < w:
        maxW = w
start, end = map(int, input().split())


def bfs(mid):
    global ans, islands, start, end
    isVisit = [False for _ in range(n+1)]
    queue = [start]
    while len(queue) != 0:
        pos = queue.pop(0)
        if pos == end:
            return True
        for i in islands[pos]:
            if isVisit[i] == True or islands[pos][i] < mid:
                continue
            isVisit[i] = True
            queue.append(i)
    return False


ans = 0
l, r = 1, maxW
while l <= r:
    mid = (l+r) // 2
    if bfs(mid) is True:
        ans = mid
        l = mid+1
    else:
        r = mid - 1

print(ans)