문제
https://www.acmicpc.net/problem/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
3 3
1 2 2
3 1 3
2 3 2
1 3
예제 출력 1
3
접근
처음에는 단순한 그래프 탐색 문제라고 생각했었다.
그래서 그냥 bfs, dfs로 구현했다가 시간 초과, 틀렸습니다 폭탄을 맞았다ㅎㅎ.... 이분 탐색을 적용할 수 있으리라고는 전혀 생각지도 못했었다가 풀이를 보고 알았다.
단순히 완전 탐색을 하면 반드시 가능한 모든 경로를 확인해본 후, 그 중에서 최대 중량이 도출되는 경로를 찾는 수밖에 없다.
반면 이분 탐색을 이용하는 방법은, 이분 탐색을 통해 중량 값 후보를 하나 선택한 후 그 중량 제한으로 이동 가능한 경로가 있는지 여부만을 확인한다. 경로 탐색 중 중량 제한이 현재의 중량 값 후보에 못 미치는 다리가 발견된다면 해당 중량으로 지나갈 수 없는 경로이니 바로 탐색을 종료할 수 있다.
만약 이동 가능한 경로가 존재하는 중량 값 후보를 찾았다면, left 값을 mid + 1로 갱신함으로써 중량을 올려 더 높은 중량을 옮길 수 있는지 확인한다.
현재 중량 후보 값으로는 이동 가능한 경로가 없다고 판별된 경우 right 값을 mid - 1로 갱신함으로써 중량을 낮춰 탐색한다.
가능한 큰 값을 찾는 upper bound 문제이므로 탐색 종료 시 right 값이 최대 중량이 된다.
틀린 구현
처음에 BFS만으로 시도했던 풀이이다.
(시간 초과뿐만 아니라 올바른 답이 나오지 않는 코드이니 시간이 많으신 게 아니면 밑으로 내려서 정답 풀이를 보시길 권합니다...)
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
List<Island>[] graph = new List[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
graph[A].add(new Island(B, C));
graph[B].add(new Island(A, C));
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
System.out.println(bfs(graph, N, start, end));
}
private static int bfs(List<Island>[] graph, int N, int start, int end) {
int maxWeight = 0;
boolean[] visited = new boolean[N + 1];
Queue<Island> q = new LinkedList<>();
q.offer(new Island(start, Integer.MAX_VALUE));
visited[start] = true;
while (!q.isEmpty()) {
Island curr = q.poll();
if (curr.num == end) {
maxWeight = Math.max(maxWeight, curr.weight);
continue;
}
for (Island neighbor : graph[curr.num]) {
if (!visited[neighbor.num]) {
visited[neighbor.num] = true;
q.offer(new Island(neighbor.num, Math.min(curr.weight, neighbor.weight)));
}
}
}
return maxWeight;
}
static class Island {
int num;
int weight;
Island (int num, int weight) {
this.num = num;
this.weight = weight;
}
}
}위 코드는 이분 탐색을 사용하지 않았기에 비효율적이기도 하거니와,
입력이
11 16
1 2 10
1 3 20
1 4 30
1 5 40
2 6 50
3 6 50
4 6 50
5 6 50
6 7 10
6 8 20
6 9 30
6 10 40
7 11 50
8 11 50
9 11 50
10 11 50
1 11위와 같이 주어졌을 때 기댓값인 40 대신 10이 출력된다.
그 이유는 bfs 과정에서의 방문 처리에 있었다.
bfs() 내에서 visited 배열은 이미 방문한 노드는 다시 큐에 넣지 않도록 하고 있다. 하지만 이미 방문한 노드더라도 해당 노드를 경유하는, 더 중량 제한이 큰 경로가 존재할 수 있기 때문에 이렇게 무턱대고 노드에 대한 방문 처리를 해서는 안 되는 거였다.
다음은 위 입력에 대해 가능한 경로의 예시이다.
경로 1: 1 → 6 → 11 (중량 10)경로 2: 1 → 5 → 6 → 11 (중량 40)
이 코드는 BFS 탐색 중 경로 1을 먼저 탐색하고, 6과 11에 대해 visited 처리가 완료된다. 경로 2는 더 높은 중량을 가지지만, 이미 방문 처리된 노드들로 인해 탐색되지 않고 종료되어 버리기 때문에 40이 출력되지 못하는 것이다.
정답
우선순위 큐 사용
이분 탐색을 적용해서 내가 처음 구현해본 풀이이다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int left = 1;
int right = 1;
List<Island>[] graph = new List[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
graph[A].add(new Island(B, C));
graph[B].add(new Island(A, C));
right = Math.max(right, C);
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
while (left <= right) {
int mid = (left + right) / 2;
if (bfs(graph, N, start, end, mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println(right);
}
private static boolean bfs(List<Island>[] graph, int N, int start, int end, int target) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
boolean[] visited = new boolean[N + 1];
pq.offer(start);
while (!pq.isEmpty()) {
int curr = pq.poll();
if (curr == end) {
return true;
}
for (Island neighbor : graph[curr]) {
if (!visited[neighbor.num] && neighbor.weight >= target) {
visited[neighbor.num] = true;
pq.offer(neighbor.num);
}
}
}
return false;
}
static class Island {
int num;
int weight;
Island (int num, int weight) {
this.num = num;
this.weight = weight;
}
}
}사실 처음에는 우선순위 큐와 visited 배열을 사용하지 않고 구현을 했었는데, 그렇게 하니 그래프에 사이클이 존재하는 경우 bfs 과정에서 큐가 비지 않아 while 문이 무한 루프를 돌 가능성이 있었다.
결국 무한 루프를 막으려면 어떻게든 방문 여부 확인을 해야 할 것 같은데, visited 배열을 그냥 사용하면 위에 작성한 것처럼 더 높은 중량의 경로가 탐색이 안 되는 문제가 있었다.
그래서 visited 배열을 사용하되, 우선순위 큐를 함께 사용해 중량이 더 큰 (우선순위가 높은) 간선을 우선적으로 탐색하도록 했다. 이렇게 하면 가장 우선순위가 높은 경로가 먼저 탐색되고, 그 이후에는 더 이상 그 경로 내 노드들에 방문할 필요가 없으니까.
간선 정렬을 통한 최적화
PriorityQueue는 내부의 원소들을 정렬된 상태로 유지해야 하기 때문에 일반적인 큐에 비해 추가적인 오버헤드가 발생할 수밖에 없다. 그래서 우선순위 큐 대신 일반 큐를 사용해 구현할 수는 없을지 찾아보았는데, 그래프 내의 각 간선을 중량 제한 값을 기준으로 내림차순 정렬하는 방식을 사용할 수 있었다. 이렇게 하면 우선순위 큐를 통해 정렬 여부를 지속적으로 관리해주지 않아도 가장 앞에 저장된 경로가 우선순위가 높기에 노드에 중복 방문을 할 필요가 없다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int left = 1, right = 1;
List<Island>[] graph = new List[N + 1];
for (int i = 1; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
graph[A].add(new Island(B, C));
graph[B].add(new Island(A, C));
right = Math.max(right, C);
}
// 그래프 간선 정렬 (가중치 기준 내림차순)
for (int i = 1; i <= N; i++) {
graph[i].sort((a, b) -> b.weight - a.weight);
}
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
while (left <= right) {
int mid = (left + right) / 2;
if (bfs(graph, N, start, end, mid)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
System.out.println(right);
}
private static boolean bfs(List<Island>[] graph, int N, int start, int end, int target) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[N + 1];
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int curr = queue.poll();
if (curr == end) {
return true;
}
for (Island neighbor : graph[curr]) {
if (!visited[neighbor.num] && neighbor.weight >= target) {
visited[neighbor.num] = true;
queue.offer(neighbor.num);
}
}
}
return false;
}
static class Island {
int num;
int weight;
Island(int num, int weight) {
this.num = num;
this.weight = weight;
}
}
}
험난했다...
탐색의 효율성을 높이기 위해 이분 탐색을 사용할 수 있다는 것도 처음 알게 되었고, 간선을 정렬하는 접근 방식도 배워갈 수 있었다.
