백준 1939. 중량제한

bbumjun·2020년 7월 2일
0

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)
profile
Wanna be a Front-end developer

관심 있을 만한 포스트

2개의 댓글

comment-user-thumbnail
2021년 2월 15일

안녕하세요. 풀이 잘봤습니다. 다름이 아니라 O(log(max(w)) * (N + M)) 이 부분에 대한 질문이 있는데요. 저는 처음에 이 문제를 bfs 만으로 풀 수 있다 생각을 했는데 시간 초과가 떠서 모든 경로를 탐색하기 때문에 그렇구나 라고 결론을 내렸는데, 알고리즘만 보면 bfs 부분이 똑같이 O( N + M) 인데, 왜 bfs 만으로는 시간초과가 나는 건지 잘 이해를 못하고 있습니다. 혹시, 제가 잘못 생각하는 부분이 있다면 지적해주시면 감사하겠습니다.

1개의 답글