백준 1446번 - 지름길 자바 풀이

문제 링크

문제 풀이 시간 : 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);
    }
}

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

1446번 - 지름길

문제 풀이 시간 : 30분

문제 요약

문제 풀이

정답 코드

다른 코드

함께 읽으면 좋은 글

5430번 - AC

1966번 - 프린터 큐

1158 - 요세푸스 문제

2164번 - 카드2