[백준] 1800번 인터넷 설치

문제 설명

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

문제 풀이

• 그래프를 BFS로 탐색하며 DP를 사용해 풀이하였다.
• 점화식은 아래와 같다

  DP[N][K] : N번 노드까지 K개의 공짜 케이블을 썼을 때 비용 최소값

• BFS로 탐색하며 현재 상태에서 공짜 케이블을 쓰는 케이스와 안쓰는 케이스를 분기하되,
  최적 부분 구조를 만족하기 위해 현재 최대 비용보다 다음 케이블의 비용이 작으면 무조건 공짜 케이블을 쓰지 않아야 한다. (다음 케이블 비용이 작은데도 공짜 케이블을 쓰는 것은 이전 선택에 영향을 주기 때문에(이전 케이블을 공짜 케이블로 대체) 최적 부분 구조를 만족하지 않는다.)

소스 코드 (JAVA)

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

public class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point {
        int n, d, k;

        public Point(int n, int d, int k) {
            this.n = n;
            this.d = d;
            this.k = k;
        }
    }

    static int N, P, K, INF = 987654321;
    static int[][] chk;
    static List<List<Point>> map = new ArrayList<>();

    static void solve() throws IOException {
        Queue<Point> q = new ArrayDeque<>();
        q.add(new Point(1, 0, 0));
        chk[1][0] = 0;
        int result = INF;
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.n == N) {
                result = Math.min(result, cur.d);
                continue;
            }
            for (int i = 0; i < map.get(cur.n).size(); i++) {
                int nextN = map.get(cur.n).get(i).n;
                int nextD = map.get(cur.n).get(i).d;
                int max = Math.max(cur.d, nextD);
                int min = Math.min(cur.d, nextD);
                //공짜 케이블을 안쓰는 케이스
                if (max < chk[nextN][cur.k]) {
                    chk[nextN][cur.k] = max;
                    q.add(new Point(nextN, max, cur.k));
                }

                //공짜 케이블을 쓰는 케이스
                if (nextD == min) continue; //다음 케이블이 현재 가격보다 쌀 경우 공짜 안쓰고 넘어감
                if (cur.k == K) continue;
                if (min < chk[nextN][cur.k + 1]) {
                    chk[nextN][cur.k + 1] = min;
                    q.add(new Point(nextN, min, cur.k + 1));
                }
            }
        }
        if (result == INF)
            result = -1;
        bw.write(result + "\n");
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        chk = new int[N+1][K+1];
        for (int i = 0; i <= N; i++) {
            map.add(new ArrayList<>());
            Arrays.fill(chk[i], INF);
        }
        for (int i = 0; i < P; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            map.get(from).add(new Point(to, dist, 0));
            map.get(to).add(new Point(from, dist, 0));
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bw.flush();
    }
}

/*
N개 위치, K개 공짜 케이블 
1 -> N까지만 연결되면 됨
남은 것중 가장 비싼 것만 가격 받음

N : 위치  (<= 1000)
P : 케이블 수 (<= 10000)
K : 공짜 갯수 (<= N)

N P K
(P개 줄)
a b d
...

dist[N][K] : 해당 위치에 K 개의 공짜 케이블을 쓰고 왔을 때 비용 최소값

 */