[Python] BOJ 1939 - 중량제한

 

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

1939번: 중량제한

# union-find로 푸는 방법과 BFS+이분탐색으로 푸는 방법 두가지가 있다.

 

I. Union-Find

   1. M개의 그래프정보를 입력받을 때 graph배열에 [-c, a, b]를 append해준다.

      (c = 중량제한, a = 시작 섬, b = 끝 섬)

   아래 코드처럼 -c로 중량제한을 받은 뒤, sort해도 되고 c로 입력받은 뒤, 내림차순 sort해도된다.

   

   2. 중량제한이 큰 정점들 부터 크루스칼 알고리즘을 통해 union(a, b)를 해준다.

      그 과정에서 공장이 있는 섬인 check(ts, te)가 True인 경우가 나오면 

      c를 출력하고 프로그램을 종료한다.

 

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
graph = []

def find(c):
	if par[c] == c:
		return c
	else:
		par[c] = find(par[c])
	return par[c]

def union(a, b):
	a, b = find(a), find(b)
	par[max(a, b)] = min(a, b)

def check(a, b):
	return find(a) == find(b)

par = [i for i in range(N+1)]
for _ in range(M):
	a, b, c = map(int,input().split())
	graph.append([-c, a, b])
ts, te = map(int,input().split())

graph.sort()
for i in graph:
	c, a, b = i[0], i[1], i[2]
	c = abs(c)
	union(a, b)
	if check(ts, te):
		print(c)
		break

----------------------------------------------------------------------------------------------------------

 

II. BFS + BinarySearch

   1. a번 섬과 연결되어있는 섬 b와 중량제한 c를 graph[a].append((b,c))로 저장해준다.

 

   2. 공장이 있는 섬 s, e 를 입력받고 low, high를 1, 10억으로 설정한다.

  

   3. 이분탐색을 통해 bfs(s, e, mid)를 실행한다. (mid = 중량제한)

      bfs(s, e, mid)가 True이면 dab에 mid를 저장해주고, 더 큰 값이 있을 수 있으니 low = mid + 1

      을 해준 뒤 이분탐색을 계속 진행한다.

      bfs(s, e, mid)가 False이면 mid값을 줄여야하므로 high = mid - 1을 해주고 이분탐색을 진행한다.

 

   # bfs함수

     x = q의 첫번째 원소

     x가 공장이 있는 섬 e라면 True를 return해준다

     graph[x]를 통해 x와 연결된 섬들을 돌며 방문하지않은 섬이고 중량제한이 w보다 같거나 크면

     방문할 수 있는 섬이므로 방문한다.  

     q가 비었는데(가능한 모든 섬을 방문 한 뒤) x가 e에 도달하지 않았으면 return False

 

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int,input().split())
graph = [[] for _ in range(N+1)]

def bfs(s, e, w):
	q = deque()
	visited = [0] * (N+1)
	visited[s] = True
	q.append(s)
	while q:
		x = q.popleft()
		if x == e:
			return True
		for i in graph[x]:
			if not visited[i[0]] and i[1] >= w:
				visited[i[0]] = True
				q.append(i[0])
	return False


for _ in range(M):
	a, b, c = map(int,input().split())
	graph[a].append((b, c))
	graph[b].append((a, c))
s, e = map(int,input().split())
low, high = 1, 1000000000
while low <= high:
	mid = (low + high) // 2
	if bfs(s, e, mid):
		dab = mid
		low = mid + 1
	else:
		high = mid - 1
print(dab)

(solved.ac 티어: 골드 4)

 

# 맨 위가 BFS+이분탐색 코드이고, 맨 아래가 Union-Find 코드이다.

   (union-find가 조금 더 효율적인 것 같다)