1446번 - 지름길

2024-03-26

#JAVA#백준

문제 링크

문제 풀이 시간 : 30분

문제 요약

•
지름길의 개수 N, 고속도로의 길이 D가 주어진다

•
N은 12 이하인 양의 정수

•
D는 10,000보다 작거나 같은 자연수

•
N개의 지름길의 시작위치, 도착위치, 길이가 주어진다.

•
D까지 이동하기 위한 거리의 최솟값을 구하라

문제 풀이

이 문제는 딱 봐도 다익스트라로 푸는 문제인 것 같다.

C++로는 다익스트라 코드를 많이 짜봤으나

자바로는 한번도 안짜본 것 같아서 이 문제를 선정했다.

근데

이 문제의 조건을 보니 굳이.. 다익스트라로 풀어야 하나 라는 생각이 나의 뇌를 지배했다.

그래서 나온 코드는

정답 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static int n,d,ans;
    public static int[][] input;

    public static void find(int sum,int road){
        if(road==d){
            ans = Math.min(sum,ans);
        }
        if(road>=d)
            return;
        for(int i=0;i<n;i++){
            find(sum+d-road,d);
            if(input[i][0]>=road){
                find(sum+input[i][2]+input[i][0]-road,input[i][1]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        input=new int[n][3];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            input[i][0]=Integer.parseInt(st.nextToken());
            input[i][1]=Integer.parseInt(st.nextToken());
            input[i][2]=Integer.parseInt(st.nextToken());
        }
        ans=d;
        for(int i=0;i<n;i++){
            if(input[i][0]<=d)
                find(input[i][0],input[i][0]);
        }
        System.out.println(ans);
    }
}

다른 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;

public class Main {
    static class node {
        int next;
        int dist;

        public node(int next, int dist) {
            this.next = next;
            this.dist = dist;
        }
    }

    static int n, d;
    static ArrayList<ArrayList<node>> arr;
    static int[] ans;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        ans = new int[d+2];
        arr = new ArrayList<>();
        for (int i = 0; i <= d; i++) {
            arr.add(new ArrayList<>());
            ans[i]=i;
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            if (start > d)
                continue;
            int dest = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            arr.get(start).add(new node(dest, dist));
        }
        find(0);
        System.out.println(ans[d]);
    }

    public static void find(int start) {
        if(start>d)
            return;

        if(ans[start+1]>ans[start]+1)
            ans[start+1]=ans[start]+1;

        for(int i=0;i<arr.get(start).size();i++){
            if(ans[arr.get(start).get(i).next] > ans[start]+arr.get(start).get(i).dist)
                ans[arr.get(start).get(i).next] = ans[start]+arr.get(start).get(i).dist;
        }
        find(start+1);
    }
}

풀고보니 다익스트라가 아니게 됐다.