[파이썬, 자바] 백준 1800 : 인터넷 설치 (골드1)

[파이썬, 자바] 백준 1800 : 인터넷 설치 (골드1)

• https://www.acmicpc.net/problem/1800

---

풀이

방향성 생각

• DFS로 node N까지 경로 메모리에 저장한다든가, 탐색을 여러 번 진행하면 TLE 발생.
• limit원까지 지불할 수 있을 때 node N까지 도달할 수 있냐 없냐를 확인한다.
• 금액 크기가 $10^6$이므로 이분탐색 20번 정도면 풀이가 가능하다.
• $O(20*NlogN)$이고 N이 크지 않아서 시간은 널널하게 풀이가 가능
• 이분탐색은 가장 비싼 간선 limit 제한이 걸렸을 때 node N까지 진행이 가능한가를 확인하고, 다익스트라는 N번 노드까지 사용한 전선의 개수를 기록한다.

 

---

파이썬

import heapq as hq
import sys


input = lambda : sys.stdin.readline().strip()
INF = float('inf')

N,P,K = map(int,input().split())

G = [[] for _ in range(N+1)]
for _ in range(P):
    a,b,cost = map(int,input().split())
    G[b].append((a,cost))
    G[a].append((b,cost))

def di(sx,limit):

    PQ = [(0,sx)]
    V = [INF]*(N+1)
    V[sx] = 0

    while PQ:
        cnt,x = hq.heappop(PQ)
        ncnt = cnt + 1

        for nx,cost in G[x]:

            if cost > limit and ncnt < V[nx]:
                V[nx] = ncnt
                hq.heappush(PQ,(ncnt,nx))
            if cost <= limit and cnt < V[nx]:
                V[nx] = cnt
                hq.heappush(PQ,(cnt,nx))

    return V[-1] <= K

answer = INF
l,r = 0,10**6+1
while l<=r:
    m = (l+r)//2
    if di(1,m):
        r = m-1
        answer = m
    else:
        l = m+1

print(answer if answer != INF else -1)

자바

import java.io.*;
import java.util.*;

public class Main {

    public static int N, P, K;
    public static List<List<int[]>> G;

    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());

        G = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            G.add(new ArrayList<>());
        }
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            G.get(a).add(new int[] { b, cost });
            G.get(b).add(new int[] { a, cost });
        }

        int answer = Integer.MAX_VALUE;
        int l = 0, r = (int) Math.pow(10, 6) + 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (di(1, m)) {
                r = m - 1;
                answer = m;
            } else {
                l = m + 1;
            }
        }

        System.out.println(answer != Integer.MAX_VALUE ? answer : -1);
    }

    public static boolean di(int sx, int limit) {

        int[] V = new int[N + 1];
        Arrays.fill(V, Integer.MAX_VALUE);
        V[sx] = 0;

        PriorityQueue<int[]> PQ = new PriorityQueue<>((cur, next) -> Integer.compare(cur[0], next[0]));
        PQ.offer(new int[] { 0, sx });

        while (!PQ.isEmpty()) {
            int[] curInfo = PQ.poll();
            int cnt = curInfo[0], x = curInfo[1];

            for (int[] nextInfo : G.get(x)) {
                int nx = nextInfo[0], cost = nextInfo[1];
                int ncnt = cnt + (cost > limit ? 1 : 0);

                if (ncnt < V[nx]) {
                    V[nx] = ncnt;
                    PQ.offer(new int[] { ncnt, nx });
                }
            }
        }
        return V[N] <= K;
    }
}

• 자바에서는 거듭제곱을 Math.pow로 구현하고 타입을 캐스팅 하는 방식을 사용한다.
• 배열 초기화 Arrays.fill 까먹지 말기.
• PQ 배열기준에서 -로 하는 방식이 직관적이지가 않아서 내부 임의의 요소 2개를 cur next로 지정하고 0번째 인덱스르 비교하는 방식으로 최소힙을 구현했다.

---

코멘트

• 이분탐색 문제들이 다른 알고리즘이랑 같이 나올 때, 얻어갈 아이디어가 많은 듯