문제 출처 : https://www.acmicpc.net/problem/1939
1939번: 중량제한
첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이
www.acmicpc.net
문제
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인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.
출력
첫째 줄에 답을 출력한다.
알고리즘 분류
풀이
2021.12.15 - [알고리즘] - [알고리즘] 크루스칼(Kruskal)과 프림(Prim)
세 가지 풀이가 가능한데,
하나는 크루스칼 알고리즘을 이용한 풀이,
하나는 프림 알고리즘을 이용한 풀이,
나머지 하나는 bfs+이분 탐색을 이용한 파라메트릭 서치 풀이이다.
크루스칼, 프림 모두 MST를 구하는 알고리즘으로, MST란 그래프 내의 모든 정점을 포함한 트리인데, 사용된 간선들의 가중치가 최소인 트리를 말한다. 즉 최소 신장 트리이다.
우선, 문제에서 중요한 부분은, 출발 노드와 도착 노드가 주어진다는 점이다.
위에서 언급했듯, 크루스칼과 프림 알고리즘은 MST를 구하는 알고리즘이다.
그리고 MST란 그래프 내의 모든 정점을 포함한 트리이다.
출발 노드와 도착 노드가 정해진 경우, 주어진 정점들을 모두 방문하지 않는 경우가 발생할 수 있다는 것이다.
따라서 크루스칼 알고리즘을 사용하지만, 엄밀히 따지면 목적은 MST를 구하는 것이 아니며,
기본적으로 모든 정점을 연결하는 MST를 구하는 크루스칼, 프림 알고리즘을 해당 문제에 적용했을 때 정상적으로 동작할지, 올바른 결과를 도출할 수 있는지 생각해 보아야 한다.
프림
프림 알고리즘 풀이부터 설명하자면, 프림 알고리즘은 현재까지 연결된 노드들에서 가중치가 최소인 간선을 선택해 다음 노드를 연결하는 방식이다. (이 문제에선 최소가 아닌 최대이기 때문에 최대 힙을 이용해야 한다.)
문제의 예제에서 1과 연결된 섬은 2,3이고,
1->2 의 중량은 2
1->3 의 중량은 3
1->~~->3을 만족하는 어떠한 경로 중, 운반할 수 있는 최대 중량을 찾아야 하기 때문에, 1->2를 가지 않고 1->3을 연결할 것이고, 답은 3이 나온다.
또 다른 예시를 들면, (양방향 간선이지만 간선이 뒤집힌 경우는 생략했다)
1->2의 중량이 10
2->3의 중량이 5
1->4의 중량이 8
4->3의 중량이 7
이라 하고, 시작점이 1, 도착점이 3이라 하자.
시작 점인 1에 연결된 간선은
1 -> 2 10
1 -> 4 8
이고, 둘 중 중량이 큰 간선 1->2를 선택해, 1과 2를 연결한다.
1,2 섬이 연결되었고, 연결된 섬에서 갈 수 있는 간선은
1 -> 4 8
2 -> 3 5
가 있다.
둘 중 중량이 큰 간선 1 -> 4를 선택해 1과 4를 연결한다.
1,2,4 섬이 연결되었고 연결된 섬에서 갈 수 있는 간선은
2 -> 3 5
4 -> 3 7
가 있다.
둘 중 중량이 큰 간선 4 -> 3을 선택해 4와 3을 연결한다.
1,2,4,3 섬이 연결되었고, 시작점에서 도착점으로 이동할 수 있다.
연결에 사용한 간선들의 중량을 최솟값은 7이 되므로, 알맞게 정답이 나온다.
크루스칼
이번엔 위의 예시에서 크루스칼 알고리즘을 수행해보자.
크루스칼 알고리즘은 간선을 오름차순 혹은 내림차순으로 정렬한 후, 간선을 순서대로 연결하는 방식이다.
간선들을 내림차순으로 정렬한다면,
1->2 10
1->4 8
4->3 7
2->3 5
와 같을 것이다. (문제에서 주어진 간선은 양방향이기 때문에 실제론 주어진 간선을 뒤집은 것도 포함하여 4개가 아닌 8개의 간선이 정렬된다.)
정렬된 간선들을 순서대로 연결한다면,
1 -> 2를 연결
(1,2) -> 4를 연결
(1,2,4) -> 3을 연결
최종적으로 1, 2, 4, 3 섬들이 연결되었고,
사용한 간선들의 중량은 10, 8, 7로 7이라는 결과가 나온다.
즉, 크루스칼 알고리즘과 프림 알고리즘 모두 굳이 방문할 필요가 없는 2번 섬을 방문할 수는 있지만, 시작 노드와 종료 노드가 최초로 연결되기 전까지 문제에서 주어진 모든 간선들의 최대 가중치만 사용하기 때문에, 항상 최선의 값을 보장한다!!!
또한, 위의 예시에선 우연히 모든 노드가 연결되었지만, 5라는 노드와 2->5 3 등의 간선이 있었다면 5는 연결되지 않았을 것이며, 이는 모든 노드를 연결해서 답이 나왔다!라는 게 아님을 설명할 수 있다.
파라메트릭 서치
파라메트릭 서치란 매개 변수 탐색으로 백준에 분류되어 있으며, 이분 탐색을 기반으로 하지만,
이분 탐색과 다른 점은, 이분 탐색은 어떠한 정렬된 리스트에서 원하는 값을 찾는 것이지만,
파라메트릭 서치는 어떠한 정렬된 리스트에서 조건에 부합하는 값을 찾는 것이다.
이 글의 본질은 문제 풀이이기 때문에 둘의 차이는 여기서 깊게 다루지 않겠다.
무튼 파라메트릭 서치는 이분 탐색을 이용해 mid라는 값이 문제의 조건에 일치하는지 검사하고, 일치한다면 이중 최적의 값을 찾아야 하는데, 문제마다 검사하는 과정은 다르다.
이 문제에선 조건에 일치하는 과정엔 bfs 알고리즘을 사용한다.
우선 우리가 찾아야 할 값은 한 번의 이동에서 옮길 수 있는 최대 중량이다.
이 값의 범위를 left~right라고 하면,
left는 중량의 최솟값인 1
right는 주어진 간선들의 중량 중 가장 큰 값이다.
이후 (left+right)/2인 mid(중량)의 짐을 가지고 있다고 할 때, 출발 섬에서 도착 섬까지 이동 가능하다면 mid는 답이 될 수 있다. 다만, 이동 가능한 중량의 최댓값을 구해야 하기 때문에, 답이 될 수 없는 mid값이 나올 때까지 mid를 증가시켜본다.
mid가 답이 될 수 있는지 확인하는 것은 bfs를 이용한다고 했는데,
이는 bfs의 시작점을 시작 섬으로 하고, 도착점을 도착 섬으로 했을 때,
mid보다 중량이 크거나 같은 간선으로 연결된 섬만 큐에 삽입하며 도착점으로 이동하는 것으로 구현이 가능하다.
시작 섬에서 시작한 노드가 도착 섬까지 무사히 도착한다면 mid는 답이 될 수 있는 것이다!
긴 풀이가 끝났다.
시간 복잡도 등을 얘기해도 좋을 것 같은데 이렇게 크루스칼과 프림 알고리즘의 비교가 가능하며, 이분 탐색 + bfs를 이용한 파라메트릭 서치까지 가능했던 좋은 문제라고 생각하여, 이러한 내용들을 중점으로 작성했다.
실제로 본인은 크루스칼과 프림 알고리즘은 MST를 구하는 데에만 사용해왔으며, 어차피 둘 중 하나로만 풀면 답이 나오니 프림 알고리즘은 대충 어떤 것이다라고 알고만 있었지 구현해본 적도 없었다.
프림 알고리즘은 정점이 적을 때 유리하고, 크루스칼 알고리즘은 간선이 적을 때 유리하다.
두 알고리즘이 모두 MST를 구하는 알고리즘이라 해도, 동작 방식의 차이가 있기 때문에 상황에 맞는 알고리즘을 적절하게 사용해야 한다는 점을 깨달았던 좋은 문제였다.
코드1(프림)
import java.util.*
import kotlin.math.*
//2 <= n<= 10000
// 1<= m <= 100000
//중량의 최댓값 구하기
//중량이 큰 다리를 탐색하여 그 중 가장 작은 값이 가능한 중량의 최댓값
fun bfs(s : Int, e : Int, edge : Array<ArrayList<Pair<Int,Int>>>, visited : BooleanArray) : Int{
var minWeight = 1987654321
visited[s]=true
val pq = PriorityQueue<Pair<Int,Int>>(kotlin.Comparator { a, b ->
when{
a.second > b.second -> 1
a.second < b.second -> -1
else -> 0
}
})
pq.add(Pair(s,1987654321))
while(pq.isNotEmpty()){
val cur = pq.poll()
minWeight = min(minWeight,cur.second)
if(cur.first==e){
break
}
visited[cur.first] =true
for(next in edge[cur.first]){
if(visited[next.first]) continue
pq.add(Pair(next.first, next.second))
}
}
return minWeight
}
fun main() = with(System.out.bufferedWriter()){
val br = System.`in`.bufferedReader()
val (n,m) = br.readLine().split(' ').map{it.toInt()}
val edge = Array(n+1){ArrayList<Pair<Int,Int>>()}
for(i in 0 until m){
val (from,to, weight) = br.readLine().split(' ').map{it.toInt()}
edge[from].add(Pair(to,weight))
edge[to].add(Pair(from,weight))
}
val (s,e) = br.readLine().split(' ').map{it.toInt()}
write("${bfs(s,e,edge,BooleanArray(n+1))}")
close()
}코드2(크루스칼)
//2 <= n<= 10000
// 1<= m <= 100000
//중량의 최댓값 구하기
data class Edge(var from : Int, var to : Int, var weight : Int)
fun getParent(x : Int,parent : IntArray) : Int{
return if(parent[x]==x) x else getParent(parent[x],parent).also{parent[x]=it}
}
fun unionParent(x : Int, y : Int, parent : IntArray){
val xx = getParent(x,parent)
val yy = getParent(y,parent)
if(xx<yy){
parent[yy]=xx
}
else{
parent[xx]=yy
}
}
fun findParent(x : Int, y : Int, parent : IntArray) : Boolean{
val xx = getParent(x,parent)
val yy = getParent(y,parent)
return xx==yy
}
fun main() = with(System.out.bufferedWriter()){
val br = System.`in`.bufferedReader()
val (n,m) = br.readLine().split(' ').map{it.toInt()}
val edge = Array<Edge>(m*2){Edge(0,0,0)}
val parent = IntArray(n+1){it}
var idx=0
for(i in 0 until m){
val (from,to,weight) = br.readLine().split(' ').map{it.toInt()}
edge[idx++] = Edge(from,to,weight)
edge[idx++] = Edge(to,from,weight)
}
val (s,e) = br.readLine().split(' ').map{it.toInt()}
edge.sortWith(Comparator { a, b ->
when{
a.weight < b.weight -> 1
a.weight ==b.weight -> 0
else -> -1
}
})
var answer=0
for(i in 0 until m*2){
if(findParent(s,e,parent))break
if(findParent(edge[i].from,edge[i].to,parent)) continue
answer= edge[i].weight
unionParent(edge[i].from,edge[i].to,parent)
}
write("${answer}")
close()
}코드3(파라메트릭 서치)
import kotlin.math.*
import java.util.*
//2 <= n<= 10000
// 1<= m <= 100000
//중량의 최댓값 구하기
//연결된 다리들 중 가장 작은 값이 가능한 중량의 최댓값
fun bfs(weight : Int, s : Int, e : Int, visited : BooleanArray, edge : Array<ArrayList<Pair<Int,Int>>>) : Boolean{
visited[s]=true
val q : Queue<Int> = LinkedList<Int>()
q.add(s)
while(q.isNotEmpty()){
val cur = q.poll()
for(next in edge[cur]){
if(next.second<weight) continue
if(visited[next.first]) continue
if(next.first==e) return true
q.add(next.first)
visited[next.first]=true
}
}
return false
}
fun main() = with(System.out.bufferedWriter()){
val br = System.`in`.bufferedReader()
val (n,m) = br.readLine().split(' ').map{it.toInt()}
val edge = Array(n+1){ArrayList<Pair<Int,Int>>()}
var right = 0
var left = 1
for(i in 0 until m){
val (from,to,weight) = br.readLine().split(' ').map{it.toInt()}
edge[from].add(Pair(to,weight))
edge[to].add(Pair(from,weight))
right = max(right, weight)
}
val (s,e) = br.readLine().split(' ').map{it.toInt()}
//mid는 내가 가지고 갈 중량
while(left<=right){
val mid = (left+right)/2
if(bfs(mid,s,e, BooleanArray(n+1),edge)){
left = mid+1
}
else{
right = mid-1
}
}
write("${left-1}")
close()
}
'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 13274 수열 Kotlin (정렬) (0) | 2021.12.14 |
|---|---|
| 백준 16398 행성 연결 Kotlin (mst) (0) | 2021.12.14 |
| 백준 2098 외판원 순회 Kotlin (비트마스킹, dp,dfs) (0) | 2021.12.12 |
| 백준 15683 감시 Kotlin (시뮬레이션) (0) | 2021.12.12 |
| 백준 10819 차이를 최대로 Kotlin (순열) (0) | 2021.12.12 |
댓글