1939 - 중량제한
정보
- 문제 보기: 1939 - 중량제한
- 소요 시간: 29분 21초
- 풀이 언어:
python - 체감 난이도: 3️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
BFS 이진탐색
풀이 코드
정보
- 메모리: 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)으로 경로가 존재하는지를 판단하는 목적이므로,
- mid가 간선 가중치를 초과하지 않고 (초과시 다리 무너짐)
- 이전에 방문한 적 없는 노드만 큐에 넣는다.
반대편 공장에 도착했다면 경로가 존재하는 것이므로, 즉시 True를 반환하고 탐색을 종료한다.