[백준 1939] 중량제한 (Python)

www.acmicpc.net/problem/1939

1939번: 중량제한

 

문제풀이

N, M : 입력값

adj_list : 섬간 인접리스트

start, end : 공장이 위치한 섬의 번호

mx, mn : 이분 탐색 범위

 

BFS와 이분 탐색을 활용한 문제였다. 처음 접해보는 유형이었고, 새로운 방식의 아이디어 및 풀이를 얻을 수 있는 문제였다.

 

1. 이분 탐색을 통해 가능한 중량을 찾는다.

- BFS 탐색을 통해 start 섬에서 end 섬으로 갈 수 있는지 확인

- 갈 수 있으면 mn을 증가시켜 start에서 end로 갈 수 있는 최고값에 근접시키기

- 불가능하다면 mx를 감소시켜 start에서 end로 갈 수 있는 값에 근접시키기

 

2. 1의 과정을 반복하면서 가능한 최대 중량을 탐색한다.

 

코드

import sys
from collections import deque

def bfs(c):
    q = deque()
    q.append(start)
    check = [False] * (N + 1)
    check[start] = True

    while q:
        x = q.popleft()
        for y, w in adj_list[x]:
            # y섬을 아직 방문하지 않았고, 현재 무게(c)로 갈 수 있으면
            if not check[y] and w >= c:
                check[y] = True
                q.append(y)
    # end 섬에 도달할 경우 True, 아니면 False
    return True if check[end] else False

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    adj_list = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        adj_list[a].append((b, c))
        adj_list[b].append((a, c))
    start, end = map(int, sys.stdin.readline().split())
    mx, mn = 1000000000, 1
    ans = 0
    while mn <= mx:
        mid = (mn + mx) // 2
        # mid 무게로 start 섬에서 end 섬으로 갈 수 있을 경우
        # ans 갱신, 최대값을 구하기 위해 mn 증가
        if bfs(mid):
            ans = mid
            mn = mid + 1
        # 못 갈 경우 mx를 줄이면서 갈 수 있는 무게 구하기
        else:
            mx = mid - 1
    print(ans)

 

결과

 

위 풀이는 'inspirit941' 님의 Python 풀이를 참고한 코드입니다.

inspirit941.tistory.com/140

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!