[BOJ - 이분탐색] 1939번 : 중량제한 (python)

 

백준 1939번 중량제한 (gold4), 이분탐색 + BFS

https://www.acmicpc.net/problem/1939

1939번: 중량제한

 

 

문제

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

 

---

 

 

1. INPUT

n 개의 섬이 있고 ,

2개의 섬을 잇는 다리가 존재하며, 그 다리엔 중량제한이 있으며

마지막에 두 섬의 번호가 입력된다.

 

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
bridges = [[] for _ in range(n+1)]

for i in range(m):
	a,b,c = map(int,input().split())
	bridges[a].append([b,c])
	bridges[b].append([a,c])
	
one, two = map(int,input().split())

 

2. 이분탐색

 

중량제한의 최소 최대값을 start와 end로 잡는다. :: C(1 ≤ C ≤ 1,000,000,000)

이분탐색의 mid는 return에 관한 정보이므로,

한 번의 이동에서 옮길 수 있는 물품들의 중량이 된다

 

중량의 최대값을 구해야 하고, 

1) 시작섬에서 끝섬까지 가는 루트가 여러개일 수 있다.

2) mid를 현재 이동시키는 중량이라고 생각했을 때 각 다리가 가능할수도 있고 아닐수도 있다.

 

result = 0 으로 초기화

 

-while start <= end:

--- mid = (start+end)//2 

 

--- 만약 bfs(mid)가 true이면

------ result = mid

# 현재 이동시키는 중량 mid가 처음 섬에서 마지막섬까지 도달할 수 있으므로 result 업데이트

------ mid = start +1

 

 

--- else    ## bfs(mid)가 false이면

------ end = mid - 1로 조절한다.

# 불가능 한것이므로, 이동시킬수 없는 중량이고,, 중량값을 줄여줘야하므로 end = mid - 1

 

 

이부분은 bfs 부분을 이해하고 돌아오면 이해가 쉬울것이다.

 

 

start = 1
end = 1000000000

result = 0
while start <= end:
	mid = (start + end) //2
	
	if bfs(mid):
		result = mid
		start = mid + 1
	else:
		end = mid - 1

 

3. BFS

이분탐색에서 mid를 인자값으로 전달, weight라는 매개변수에 할당한다.

weight(mid)는 옮기는 최대 중량이라 가정하고, 시작섬부터 끝섬까지 옮겨봐야한다.

 

일단 시작섬에서 끝섬까지 갈수 있는지를 먼저 체크해야하므로 

- queue 를 만들고, 시작섬을 넣는다.

- visited 리스트를 False로 초기화 한 후 , visited[시작섬] = True

- 큐가 빌때까지 반복,

--- 큐에서 노드를 빼고,

--- 연결된 섬(i) 만큼 반복 

--- 방문 X 이면서 i라는 섬에 가는데에 w가 최대 중량이므로 w >= weight 이면 옮길 수 있는것이므로

------ i를 방문처리, 큐에 넣어준다. 

 

-큐가 비면 반복문을 나오고 나면 visited가 update 되어 있을 것.

 

visited[마지막섬] 이 True  값이면 return True

아니면 return False 를 해줘서 

 

mid 값이 마지막섬까지 도달할 수 있는지를 체크한다.

 

def bfs(weight): # weight == now
	queue = deque()
	queue.append(one)
	visited = [False] * (n+1)
	visited[one] = True
	
	while queue:
		x= queue.popleft() # w == limit
		
		for i,w in bridges[x]:
			if not visited[i] and w >= weight:
				visited[i] = True
				queue.append(i)
	
	if visited[two]: return True
	else: return False

 

 

 

 

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(weight): # weight == now
	queue = deque()
	queue.append(one)
	visited = [False] * (n+1)
	visited[one] = True
	
	while queue:
		x= queue.popleft() # w == limit
		
		for i,w in bridges[x]:
			if not visited[i] and w >= weight:
				visited[i] = True
				queue.append(i)
	
	if visited[two]: return True
	else: return False
	
n, m = map(int,input().split())
bridges = [[] for _ in range(n+1)]

for i in range(m):
	a,b,c = map(int,input().split())
	bridges[a].append([b,c])
	bridges[b].append([a,c])
	
one, two = map(int,input().split())

start = 1
end = 1000000000

result = 0
while start <= end:
	mid = (start + end) //2
	
	if bfs(mid):
		result = mid
		start = mid + 1
	else:
		end = mid - 1
		
print(result)