[백준 Gold 5] 1446 지름길 - Java

문제 링크 : www.acmicpc.net/problem/1446

1446번: 지름길

 

접근 과정 

• 문제 유형은 다익스트라이지만, DP가 어울릴 것이라 생각하여 DP로 접근
• DP[n] : 위치 n까지 이동한 최소 거리
• HashMap<Integer, List<int[]>> ShortCut에 <도착 위치, List(출발 위치, 이동 거리)>의 형식으로 지름길을 저장
• Top-Down 과 Bottom-Up의 2가지 방식으로 DP(N)을 구하여 반환.

 

소스 코드 및 결과

  Code 1 : Top-Down

import java.io.*;
import java.util.*;
/* 
    지름길
    Top-Down
*/
public class BOJ1446 {

    static int[] dp; // 위치가 n일 때의 최소 이동거리
    static HashMap<Integer, List<int[]>> shortCut; // key : 도착지점, value : (출발지점,이동거리)리스트 형식의 지름길 정보

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        shortCut = new HashMap<>();

        while (N-- > 0) { // 지름길 정보를 shortCut에 저장
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());

            if(!shortCut.containsKey(to)){
                shortCut.put(to, new ArrayList<>());
            }
            shortCut.get(to).add(new int[]{from,dist}); // 지름길의 도착 위치를 Key값으로 지정

        }

        dp = new int[D+1]; // dp 초기화

        System.out.println(findDP(D)); 
        
    }

    static int findDP(int n){

        if (n == 0) { // 위치지점이 0
            return 0;
        }

        if (dp[n] != 0) { // 이미 계산된 최소거리
            return dp[n];
        }

        int temp = findDP(n-1) + 1; // 기본값은 현재위치-1에서의 최소거리 + 1

        if (shortCut.containsKey(n)) {
            for(int[] root : shortCut.get(n)){
                temp = Math.min(temp, findDP(root[0])+root[1]);
            } 
            // 도착지점이 n인 지름길을 이용했을 경우를 조사하여, 최소값 갱신
        }

        dp[n] = temp;

        return dp[n];
    }    
}

 

결과 : 

 

  Code 2 : Bottom-Up

import java.io.*;
import java.util.*;
/* 
    지름길
    bottom-up 
*/
public class BOJ1446 {

    static int[] dist; // 위치가 n일 때의 최소 이동거리 
    static HashMap<Integer, List<int[]>> shortCut; // key : 도착지점, value : (출발지점,이동거리)리스트 형식의 지름길 정보

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int D = Integer.parseInt(st.nextToken());

        shortCut = new HashMap<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            if (!shortCut.containsKey(to)) {
                shortCut.put(to, new ArrayList<>());
            }
            shortCut.get(to).add(new int[]{from,distance});
        }

        dist = new int[D+1]; // dist 초기화

        for(int i = 1; i<=D; i++){  // 위치 1부터 시작하여 D위치까지 최소 이동거리를 채움
            int d = dist[i-1]+1; // 기본값 : (현재 위치-1)에서의 최소 이동거리 + 1

            if (shortCut.containsKey(i)) {
                for(int[] root : shortCut.get(i)){
                    // 도착위치가 i인 지름길을 조회해서 최소 이동거리 갱신
                    d = Math.min(d, dist[root[0]]+root[1]);
                }
            }

            dist[i] = d;            
        }

        System.out.println(dist[D]);
    }
}

 

결과 :