문제 풀이
A번 교차로에서 B번 교차로까지 C원을 가지고 가려고 한다.
이 때 교차로 사이 골목을 지날때마다 통행료를 내야 한다.
전체 통행료가 커질수록 수치심(골목에서 내는 최대 통행료)가 작아지고, 전체 통행료가 작아질수록 수치심은 커진다.
수치심을 최소로 하고 싶고, 내가 가진 C원으로 목적지까지 도달하고 싶다. 이 경우 전체 통행료를 최대한 크게 했을 때 골목 요금 중 최댓값을 출력하는 문제이다.
(즉, 전체 통행료가 최대인 상황에서 거치는 골목에서 내는 통행료 중 최댓값을 반환)
문제 풀이
문제 자체가 전체 통행료를 "최대로 했을 때" "최소가 되는 골목 통행료"를 구하는 문제이다.
최대인 상황에서의 최소값을 구하는 문제? 바로 이분 탐색을 해결할 수 있는 문제라는 것을 파악할 수 있어야 한다.
문제는 두 가지가 존재한다.
1. 최대 요금 C 이하인 경우라는 것을 증명해야 한다.
2. 이분 탐색의 left와 right을 무엇으로 설정해야 하는가?
먼저 2번부터 생각해보았다. 우리가 결국 구해야 하는 것은 "지나가는 골목의 통행료"의 최솟값이다.
따라서, left와 right을 "골목 1개의 통행료"와 연관있는 값으로 설정하면 될 것 같다고 생각했다.
따라서, 나는 left = 0, right를 골목 1개 통행료 중 최댓값으로 설정했다.
그리고 mid값을 설정하여 만약 골목의 통행료가 mid보다 크면 해당 골목은 통제되고 있는(지나가지 못하는) 골목이라고 생각했다.
만약 mid를 설정하여 C 안에 도착할 수 있다면 답이 될 수 있는 후보이다.
따라서 값을 저장해주고, "최솟값"을 구하고 싶기 때문에 right = mid - 1로 설정해준다.
반대의 경우 답이 될 수 없으므로 left = mid + 1로 제한 요금을 조금 더 널널히 해준다.
1번 조건은 조금 생각하기가 까다로웠다.
결국 이 문제는 그래프 문제라고 생각하였고, A -> B 지점으로 가는 "최소 cost"를 구하는 문제라고 생각하였다.
최소 cost를 구하는 알고리즘 중 가장 유명하고 코딩 테스트에서 많이 활용되는 Dijkstra Algorithm을 활용하기로 했다.
다익스트라 알고리즘을 활용하여 A -> B지점으로 가는 최소 요금을 계산하고, 이 금액을 C와 비교하는 것이다.
이 때 우선순위 큐와 방문 여부를 확인하는 배열을 활용하여 A -> T(T는 중간 지점)로 가는 cost가 작은 것부터 출력하여 값을 갱신하는 방법으로 다익스트라 알고리즘을 구현하였다.
코드
import java.io.*;
import java.util.*;
class Point implements Comparable<Point>{
long cost;
int point;
public Point(long cost, int point) {
this.cost = cost;
this.point = point;
}
@Override
public int compareTo(Point p) {
return Long.compare(this.cost, p.cost);
}
}
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, M, A, B;
static long C;
static ArrayList<Point>[] lists;
static long[] Dijkstra(long max_cost) {
long[] arr = new long[N+1];
boolean[] visit = new boolean[N+1];
for(int i = 1;i<N+1;i++) arr[i] = Long.MIN_VALUE;
arr[A] = 0;
PriorityQueue<Point> queue = new PriorityQueue<>();
queue.add(new Point(0, A));
while(!queue.isEmpty()) {
Point point = queue.poll();
if(visit[point.point]) continue;
// 이미 방문하여 cost를 update한 지점. 갱신 과정 불필요
visit[point.point] = true;
// 이번 while문 실행 때 cost를 갱신할 것이므로 방문 여부 체크
for(Point tmp:lists[point.point]) {
if(tmp.cost>max_cost) {
// 우리는 max_cost보다 큰 통행료를 내는 길은 갈 수 없다
// 따라서 이 경우는 무시해준다
continue;
}
long sum = arr[point.point]+tmp.cost;
// A -> point.point -> tmp.point로 이동하는 cost
// (arr[point.point]) (tmp.cost)
if(!visit[tmp.point]
&& sum <= C && arr[tmp.point] < sum) {
// tmp.point를 방문하지 않았으며, 전체 cost가 보유 자금인
// C 이하이며 A -> tmp.point cost로 저장되어 있는 값보다
// sum이 작을 경우에 우선순위 큐에 넣어줌
arr[tmp.point] = sum;
queue.add(new Point(tmp.cost, tmp.point));
}
}
}
return arr;
}
public static void main(String[] args) {
FastReader sc = new FastReader();
N = sc.nextInt();
M = sc.nextInt();
A = sc.nextInt();
B = sc.nextInt();
C = sc.nextLong();
lists = new ArrayList[N+1];
for(int i =1;i<N+1;i++) {
lists[i] = new ArrayList<>();
}
long max = Long.MIN_VALUE;
for(int i =0;i<M;i++) {
int s = sc.nextInt();
int e = sc.nextInt();
long c = sc.nextLong();
max = Math.max(max, c);
lists[s].add(new Point(c, e));
lists[e].add(new Point(c, s));
}
long left = 0;
long right = max; // 골목 통행료 중 최댓값
long ans = -1;
while(left <= right) {
long max_cost = (left+right)/2;
// 내가 설정할 낼 수 있는 골목 통행료 중 최댓값
long[] arr = Dijkstra(max_cost);
if(arr[B]==Long.MIN_VALUE) {
// A -> B로 가는 경로가 존재하지 않는 경우
// max_cost를 증가시켜야 하므로 left = max_cost + 1 시킴
left = max_cost + 1;
}
else {
// A -> B로 가는 경로가 존재하는 경우
// 답의 후보가 될 수 있으므로 ans에 max_cost를 저장한다.
// 또한, 이보다 더 작은 max_cost가 존재할 수도 있으므로
// right = max_cost - 1으로 다시 이분 탐색을 실시한다.
right = max_cost - 1;
ans = max_cost;
}
}
System.out.println(ans);
}
static class FastReader // 빠른 입력을 위한 클래스
}결과
-
런타임 에러 : 보유한 돈인 C는 long 범위의 값을 가진다.
-
부분 점수(42/43) : arr, 즉 A -> B로 가는 cost의 범위는 long 범위의 값이다. 따라서 우리는 long[] arr로 배열을 선언하였다.
글너데 arr 값을Long.MIN_VALUE가 아닌Integer.MIN_VALUE로 설정하여 범위에 의한 에러가 발생하였다.
