[BOJ] 1800번: 인터넷 설치
문제 Gold 5
풀이
이분 탐색 + 다익스트라!
정답이 될 수 있는 값을 이분 탐색으로 정한 후, 검증위해 다익스트라를 활용
이분탐색
- left는 정답이 될 수 있는 최솟값 0, right는 정답이 될 수 있는 최댓값으로 설정(입력 시, 미리 받아놓음)
- 중간값으로 다익스트라
connectOK()
를 돌림- 유효하다면, 일단 답으로 설정하고 범위를 좀 더 작은값으로 해서 다시 검사
- 아니라면, 좀 더 큰 범위에서 다시 검사
✔ 결과값이 0이 될 수 있음을 고려하고, 마지막 출력 조건을 잘 설정하자..!
다익스트라
cost의 기준: K보다 크면 +1의 비용, 아니면 0
+1의 비용을 최대한 안거치는 쪽으로 설정되어 유효한 답이 될 수 있음
💡 dist[N-1] 에는 결국 K보다 큰 비용의 경로를 최소한으로 거쳤을 때, 몇 개를 거쳤는지 알 수 있게 됨
코드
package shortestPath;
import java.util.*;
import java.io.*;
public class BOJ_1800_인터넷설치 {
static int N, P, K;
static List<int[]>[] connect;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
connect = new List[N];
for(int i = 0 ; i < N ; i++) connect[i] = new ArrayList<>();
int max = Integer.MIN_VALUE;
for(int i =0 ; i < P ; i++){
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken())-1;
int f = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken());
connect[t].add(new int[]{f, c});
connect[f].add(new int[]{t, c});
max = Math.max(max, c);
}
int left = 0; // 정답이 될 수 있는 최솟값
int right = max; // 정답이 될 수 있는 최댓값
int res = Integer.MIN_VALUE;
while(left <= right){ // 종료 조건: 왼쪽 포인터가 오른쪽 포인터보다 크거나 같아질 때
int mid = (left+right) / 2; // 중간값 설정
if(connectOK(mid)){ // mid 값이 답이 될 수 있다면
res = mid; // 일단 답으로 설정
right = mid - 1; // 좀 더 작은 값은 안되는지 다시 검사
} else{ // 답이 안된다면
left = mid + 1; // 좀 더 큰 값으로 다시 검사
}
}
System.out.println((res == Integer.MIN_VALUE)?-1:res);
}
private static boolean connectOK(int mid) {
int[] dist = new int[N];
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->Integer.compare(o1[1], o2[1]));
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
pq.offer(new int[]{0, 0});
while(!pq.isEmpty()){
int[] cur = pq.poll();
int n = cur[0];
int c = cur[1];
if(dist[n] < c) continue;
for(int[] i : connect[n]){
int cost = (i[1] > mid)? c+1 : c; // K보다 크면 +1, 안크면 0
if(cost < dist[i[0]]){
dist[i[0]] = cost;
pq.offer(new int[]{i[0], cost});
}
}
}
return dist[N-1] <= K; // dist[N-1] == K보다 큰 비용 경로의 개수
}
}
제출
package shortestPath;
import java.util.*;
import java.io.*;
public class BOJ_1800_인터넷설치 {
static int N, P, K;
static List<int[]>[] connect;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
connect = new List[N];
for(int i = 0 ; i < N ; i++) connect[i] = new ArrayList<>();
int max = Integer.MIN_VALUE;
for(int i =0 ; i < P ; i++){
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken())-1;
int f = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken());
connect[t].add(new int[]{f, c});
connect[f].add(new int[]{t, c});
max = Math.max(max, c);
}
int left = 0; // 정답이 될 수 있는 최솟값
int right = max; // 정답이 될 수 있는 최댓값
int res = Integer.MIN_VALUE;
while(left <= right){ // 종료 조건: 왼쪽 포인터가 오른쪽 포인터보다 크거나 같아질 때
int mid = (left+right) / 2; // 중간값 설정
if(connectOK(mid)){ // mid 값이 답이 될 수 있다면
res = mid; // 일단 답으로 설정
right = mid - 1; // 좀 더 작은 값은 안되는지 다시 검사
} else{ // 답이 안된다면
left = mid + 1; // 좀 더 큰 값으로 다시 검사
}
}
System.out.println((res == Integer.MIN_VALUE)?-1:res);
}
private static boolean connectOK(int mid) {
int[] dist = new int[N];
PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->Integer.compare(o1[1], o2[1]));
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
pq.offer(new int[]{0, 0});
while(!pq.isEmpty()){
int[] cur = pq.poll();
int n = cur[0];
int c = cur[1];
if(dist[n] < c) continue;
for(int[] i : connect[n]){
int cost = (i[1] > mid)? c+1 : c; // K보다 크면 +1, 안크면 0
if(cost < dist[i[0]]){
dist[i[0]] = cost;
pq.offer(new int[]{i[0], cost});
}
}
}
return dist[N-1] <= K; // dist[N-1] == K보다 큰 비용 경로의 개수
}
}
result값이 0이 될 수 있다는 것을 고려하지 못했었다..!
Author And Source
이 문제에 관하여([BOJ] 1800번: 인터넷 설치), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dot2__/BOJ-1800번-인터넷-설치저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)