[BOJ] 1939번 - 중량제한

삼성 문제 몇 개를 풀다가 시간초과 때문에 안 되던 것들 때문에 기분 전환 하고자, 이분탐색 문제를 풀었다.

파이썬 시간도 충분히 고려해 주기 때문에 내 로직이 틀렸다고 생각했고, 다른 문제들을 풀어봄으로써 다시 실력을 쌓아야할 것 같았다.

 

이번 문제에서는 단순 BFS 와 이분탐색 두 가지를 합쳐놓은 것을 바탕으로 문제가 출제 되었다.

보통 이분탐색 문제는 구하고자 하는 것의 참과 거짓을 판별해서 항상 답을 구해왔던 것 같다. 

역시 이 문제도 마찬가지로 탐색하고자 하는 중량이 끝점까지 도달하냐 못하냐를 중심으로 구했다.

맨 처음 봤을 때 " 어떤식으로 이분탐색을 할까? " 이 생각까지 시간이 좀 걸렸다. 역시 많이 풀어봐야하나.. 느꼈다.

방법을 알고나니 코드 짜는 것은 그리 어렵지 않아 금방 짰다. 

 

www.acmicpc.net/problem/1939

1939번: 중량제한

섬 개수가 10만개 까지 나올 수 있으므로 10만*10만 리스트를 만들어버리게 되면 메모리 초과가 날 수 있기 때문에

입력 받는 부분만 정보를 저장하는 방식으로 했다.

 

1. 이분탐색을 위해 시작과 끝 중량을 잡는다.

 

2. bfs() 함수에서 섬의 시작점에서 끝 점까지 매개변수로 입력받은 중량을 넘지 않고 끝점 까지 갈 수 있는지 판단한다.

 

3. 이분탐색을 하면서 bfs()를 실행한다. 만족 한다면 l = mid + 1을 통해 범위를 줄여준다.

-> 이유: 더 큰 범위의 mid값을 판별하면서 최대 중량을 구해야하기 때문에

 

from sys import stdin

std = stdin.readline
N, M = map(int, std().split())
island = [[]for i in range(N)]

for i in range(M):
    a, b, d = map(int, std().split())
    island[a-1].append((b-1, d))
    island[b-1].append((a-1, d))

start, end = map(int, std().split())
start, end = start-1, end-1


def bfs(d):
    q = []
    check = [0 for i in range(N)]
    q.append(start)
    check[start] = 1
    while q:
        ver = q.pop(0)
        for v in island[ver]:
            go, distance = v
            if distance >= d and check[go] == 0:
                q.append(go)
                check[go] = 1
    if check[end] == 1:
        return True
    return False


l, r = 0, 1000000000
answer = 0
while l <= r:
    mid = (l+r)//2
    result = bfs(mid)
    if not result:
        r = mid-1
    else:
        if mid > answer:
            answer = mid
        l = mid+1

print(answer)