Skip to main content

1939 - 중량제한

info
  • 문제 보기: 1939 - 중량제한
  • 소요 시간: 29분 21초
  • 풀이 언어: python
  • 체감 난이도: 3️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

BFS 이진탐색


풀이 코드​

info
  • 메모리: 59144 KB
  • 시간: 416 ms
import sys
from collections import deque
input = sys.stdin.readline

n, m = 0, 0
start, end = 0, 0
graph = []
low, high = 0, 0 # binary search

def bfs(visited, mid):
    q = deque()
    q.append(start)
    while q:
        v = q.popleft()
        if v == end: # end 도착 -> 경로 있음!
            return True
        
        for (b, c) in graph[v]: # end 아니면 인접한 곳으로 이동
            # 중량 제한 안걸리고 방문한 적 없으면
            if mid <= c and visited[b] == False:
                visited[b] = True
                q.append(b) # 이동
    
    return False # 경로 없음


def bsearch():
    global low, high
    
    while (low <= high):
        # 최대중량후보를 mid로 설정하고,
        # bfs로 start -> end까지의 경로가 있는지 확인
        visited = [False for _ in range(n+1)]
        mid = (low + high) // 2
        exist = bfs(visited, mid)
        if exist:
            low = mid + 1
        else:
            high = mid - 1
    
    return high


def solution():
    global n, m, start, end, graph, high
    
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
        high = max(high, c) # 다리 중 최대 중량
        
    start, end = map(int, input().split()) # 공장 위치
    
    print(bsearch())


if __name__ == '__main__':
    solution()

풀이 해설​

💭 문제를 읽고 든 생각​

1. "최대 중량 다리를 고르는게 무조건 이득이네"​
  • 최대 가중치 경로를 구하는 것과 같다는 생각
2. "이진탐색 써야할 것 같은데?"​
  • C의 범위 값이 1,000,000,000 이면 대놓고...

생각 정리​

레퍼를 찾아보니 이진탐색을 사용하는 로직은 bfs도 같이 수행하더라.

(솔직히 bfs 큐가 메모리제한 버티는지는 아직 감을 못잡음)

하지만 각각을 어떻게 사용해야 할까?

-> 문제에서 구하고자 하는 것은 최대 중량이므로, 이를 이진탐색으로 구하는 것은 맞다.

-> 다만, 그 중량으로 두 공장 간의 경로가 존재하느냐가 관건이다. 그러니 이를 bfs로 판단하자.


1️⃣ 이진탐색 로직​

def bsearch():
    global low, high
    
    while (low <= high):
        # 최대중량후보를 mid로 설정하고,
        # bfs로 start -> end까지의 경로가 있는지 확인
        visited = [False for _ in range(n+1)]
        mid = (low + high) // 2
        exist = bfs(visited, mid)
        if exist:
            low = mid + 1
        else:
            high = mid - 1
    
    return high

bfs를 통해 경로가 존재하는지의 여부를 exist로 반환한다.

경로가 존재한다면 좀 더 큰 중량 후보값(mid)을 탐색하고,

존재하지 않는다면 중량 후보값을 줄여본다.


2️⃣ BFS 로직​

def bfs(visited, mid):
    q = deque()
    q.append(start)
    while q:
        v = q.popleft()
        if v == end: # end 도착 -> 경로 있음!
            return True
        
        for (b, c) in graph[v]: # end 아니면 인접한 곳으로 이동
            # 중량 제한 안걸리고 방문한 적 없으면
            if mid <= c and visited[b] == False:
                visited[b] = True
                q.append(b) # 이동
    
    return False # 경로 없음

주어진 중량(mid)으로 경로가 존재하는지를 판단하는 목적이므로,

  1. mid가 간선 가중치를 초과하지 않고 (초과시 다리 무너짐)
  2. 이전에 방문한 적 없는 노드만 큐에 넣는다.

반대편 공장에 도착했다면 경로가 존재하는 것이므로, 즉시 True를 반환하고 탐색을 종료한다.