1939번: 중량제한
첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리
www.acmicpc.net
0. 다익스트라나 프림에서 사용하는 방식을 사용했다.
1. 시작지점의 초기값은 MAX, 나머지 지점의 초기값은 0
2. 아직 가보지 못한 지점중, 가장 많은 짐을 지고 갈수있는 지점 X를 탐색한다
3. X로부터 갈수있는 지점들을, X를 거치는 경우 / 기존 최댓값을 비교해 갱신한다
4. 이를 n번 반복하면, n개의 노드 전체를 탐색한 것이다.
5. 종료된 후 end지점에 있는 값이 해당 지점에 들고갈 수 있는 최대 짐 무게이다
* 성능 향상법 : n에 비해 m의 크기가 크지 않으므로, 우선순위 큐를 이용해 최대값을 찾는다면 시간 성능이 올라갈 것이다
* 다른 풀이법 : 짐의 무게가 N일때, cost가 N 이상인 다리만 사용해서 시작점 - 도착점에 도달할 수 있는 최대 N 구하기
- N에 대해 bfs를 실행해보며 이분탐색으로 N값을 갱신한다
* 문제 태그에 disjoint set이 있던데.. 모르겠다
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = pint(st.nextToken());
int m = pint(st.nextToken());
ArrayList<ArrayList<int[]>>graph=new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int n1 = pint(st.nextToken());
int n2 = pint(st.nextToken());
int c = pint(st.nextToken());
graph.get(n1).add(new int[] {n2,c});
graph.get(n2).add(new int[] {n1,c});
}
st = new StringTokenizer(br.readLine(), " ");
int fst = pint(st.nextToken());
int end = pint(st.nextToken());
//각 지점까지 도달할 수 있는 최대 무게, 초깃값 0
int[]weight = new int[n+1];
boolean[]isV=new boolean[n+1];
weight[fst]=Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int max=0,maxNode=0;
for (int j = 0; j <= n; j++) {
if(!isV[j] && max<weight[j]) {
max=weight[j];
maxNode=j;
}
}
isV[maxNode]=true;
for (int j = 0; j < graph.get(maxNode).size(); j++) {
int[]next = graph.get(maxNode).get(j);
int nextCost=Math.min(next[1], weight[maxNode]);
if(weight[next[0]] <nextCost) {
weight[next[0]]=nextCost;
}
}
}
System.out.println(weight[end]);
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글
| [백준] 1062 - 가르침 (0) | 2021.05.05 |
|---|---|
| [백준] 17404 - RGB거리 2 (0) | 2021.05.02 |
| [백준] 10775 - 공항 (0) | 2021.05.01 |
| [백준] 16562 - 친구비 (0) | 2021.04.28 |
| [백준] 3055 - 탈출 (0) | 2021.04.28 |
| [백준] 4195 - 친구 네트워크 (0) | 2021.04.28 |
| [백준] 1976 - 여행 가자 (0) | 2021.04.28 |