[백준] 1800번: 인터넷 설치 - JAVA

🔗 문제 링크

BOJ 1800번: 인터넷 설치

1800번: 인터넷 설치

 

📝 풀이 과정

처음에는 방문할 때마다 가격을 저장하고 해당 가격순으로 정렬하여 K개만큼 제외하는 등의 작업이 굉장히 오래걸렸기 때문에 당연하게도 시간초과가 발생했다...

 

계속 고민하며 아이디어가 떠오르지 않아 고생하던 중 한가지 힌트를 보게 되었다. 최소값을 미리 정한 뒤 탐색을 하라는 것이었다.

 

 

최소값을 x로 두고 가격이 x이하인 선은 그냥 연결을 하고, x이상인 선은 K개까지 무료로 연결할 수 있으므로 연결을 하도록 체크해주었다. DFS를 돌다가 N번 컴퓨터를 만나게 되면 해당 최솟값으로 연결을 할 수 있는 경우라고 판단했기 때문에 true를 반환했고, 만약 끝까지 N번을 만나지 못한다면 연결할 수 없는 경우라고 판단해 false를 반환하였다.

 

또한, 적절한 최소값을 가질 경우를 판별하기 위해 0 ~ 1,000,000까지의 가격을 이분탐색을 통해 최소값의 범위를 지정해주었다. 탐색 결과가 true라면 더 작은 최소값을 가질 때 탐색이 가능한지 알기 위해 end값을 변경해주었고, false라면 최소값을 올리기위해 start의 값을 변경해주었다.

 

❓ 최소값이 0인 경우?
N번 컴퓨터까지 도달하는데 간선이 K개 이하만큼 연결해도 가능한 경우로 K개까지 무료로 연결이 가능하기 때문에 돈을 지불하지 않고도 인터넷 설치가 가능하다

 

💻 코드

import java.util.*;

public class Main {
    static int N, P, K, ans = Integer.MAX_VALUE;
    static ArrayList<int[]>[] adj;
    static boolean[] costCheck;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        P = sc.nextInt();
        K = sc.nextInt();

        adj = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++)
            adj[i] = new ArrayList();

        for (int i = 0; i < P; i++) {
            int n1 = sc.nextInt(), n2 = sc.nextInt(), cost = sc.nextInt();

            adj[n1].add(new int[]{n2, cost});
            adj[n2].add(new int[]{n1, cost});
        }

        divide(0, 1000000);

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

    static void divide(int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;

            if (dfs(mid)) {
                ans = mid;
                end = mid - 1;
            } else
                start = mid + 1;
        }
    }

    static boolean dfs(int x) {
        Deque<int[]> stack = new ArrayDeque();
        boolean[][] visit = new boolean[N + 1][K + 1];

        stack.push(new int[]{1, K});

        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            if (cur[0] == N) return true;

            if (visit[cur[0]][cur[1]]) continue;
            visit[cur[0]][cur[1]] = true;

            for (int[] a : adj[cur[0]]) {
                if (a[1] <= x) stack.push(new int[]{a[0], cur[1]});
                else if (cur[1] > 0) stack.push(new int[]{a[0], cur[1] - 1});
            }
        }

        return false;
    }
}

 

📊 제출 결과