문제풀이/백준
[JAVA] BOJ 백준 1939번 - 중량제한
그적
2024. 1. 3. 16:04
목차
- 문제
- 내가 푼 방법
- 자바 코드
- 결과 및 회고
1. 문제
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
2. 내가 푼 방법
특정 노드에서 특정 노드로 이동할 수 있는 다익스트라 알고리즘을 떠올렸다. 하지만 최대 가중치를 가지는 경로를 찾는다는 점에서 조금 변형된 문제이다.
시작 정점 s에서 다른 정점까지 갈 수 있는 최대 가중치를 dist 배열에 저장해 두었다. 이 최대 가중치들은 이동한 간선들의 최소 값을 특정하므로 현재까지의 가중치(w)와 이동하려는 정점의 가중치(tuple.w) 중에서 작은 값을 선택해야 한다.
public static void solution() {
PriorityQueue<Tuple> queue = new PriorityQueue<>();
queue.add(new Tuple(s, Integer.MAX_VALUE));
int[] dist = new int[N+1];
while (!queue.isEmpty()) {
Tuple t = queue.poll();
int v = t.v;
int w = t.w;
if (dist[v] > w) continue;
if (v == e) {
result = Math.max(result, w);
continue;
}
for (Tuple tuple : list[v]) {
if (dist[tuple.v] < Math.min(w, tuple.w)) {
dist[tuple.v] = Math.min(w, tuple.w);
queue.add(new Tuple(tuple.v, dist[tuple.v]));
}
}
}
}
3. 자바 코드
깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1939.java
import java.util.*;
import java.io.*;
class Main {
static int N;
static List<Tuple>[] list;
static int s, e;
static int result;
public static void main(String[] args) throws IOException {
input();
solution();
output();
}
public static void solution() {
PriorityQueue<Tuple> queue = new PriorityQueue<>();
queue.add(new Tuple(s, Integer.MAX_VALUE));
int[] dist = new int[N+1];
while (!queue.isEmpty()) {
Tuple t = queue.poll();
int v = t.v;
int w = t.w;
if (dist[v] > w) continue;
if (v == e) {
result = Math.max(result, w);
continue;
}
for (Tuple tuple : list[v]) {
if (dist[tuple.v] < Math.min(w, tuple.w)) {
dist[tuple.v] = Math.min(w, tuple.w);
queue.add(new Tuple(tuple.v, dist[tuple.v]));
}
}
}
}
public static class Tuple implements Comparable<Tuple> {
int v;
int w;
public Tuple(int v, int w) {
this.v = v;
this.w = w;
}
@Override
public int compareTo(Tuple t) {
return t.w - this.w;
}
}
public static void output() throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(result+"");
bw.flush();
bw.close();
}
public static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
list = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
list[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
list[a].add(new Tuple(b, w));
list[b].add(new Tuple(a, w));
}
st = new StringTokenizer(br.readLine());
s = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
br.close();
}
}
4. 결과 및 회고
if 문에서 비교하는 대상들이 헷갈렸었는데,, 뇌를 장착하고 제대로 푸니까 바로 해결할 수 있었다.