백준 No.1446 지름길 - JAVA

 

 

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D 킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커므가 많아서 정말 운전하기도 힘들다. 어느 날 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행 할 수는 없다.

 

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

 

 

틀린 점

- 처음에 dist 배열에 크기가 정말 고민이었는데 문제에서 10000을 넘기지 않는다 하여 10000을 주고 풀어봤는데 그러기에는 인접리스트 크기도 같게 줘야했기에 이렇게 가다가 분명 메모리 초과 또는 시간 초과로 틀릴 거 같아 계속 시도하다가 답을 봐버렸다....

 

 

 

풀이

dist 배열을 10001의 크기에 모두 10001로 초기화 시킨다. 그리고 Node에 vertex와 가중치만 받는 것이 아닌 세가지 모두를 받도록 변경한다.

그리고 값을 입력받을 때 걸러야 할 값들이 있는데

1. 목표치  보다 더 나간 지름길 걸러야 하낟.

2.  지름길이 아닌 길도 걸러야 한다 -> 50 -> 100 이면 그냥 걸아가도 50인데 가중치가 60으로 나와버리면 지름길이 아니다.

 

index와 move 변수를 생성한다. index는 리스트에 접근하기 위한 인덱스이고 move는 계속 1칸씩 또는 지름길을 타는 변수이다.

while문을 돌리는데 move가 도착지점에 갈때까지 돌린다. 

 while문 안에서 일단 index는 당연히 list에 접근해야 하므로 list 크기보다 작아야 한다. 

그렇게 if문 안에 들어와서 list에 데이터를 index변수를 통해 꺼낸다. 

move 값이 데이터에 시작부분과 동일하다면 최단거리를 기록하는 해당 위치에 표시해준다. dist[r.end]  에 값을 넣어주면 된다.

 

dist[r.end] 에 들어가는 값은 dist[move]+r.cost, dist[r.end] 중 작은 값이 들어간다. .

dist[move]는 현재까지 온 거리 가중치이고 여기에 지름길의 가중치를 더한 값을 dist[목적지]에 넣어준다. 

근데 여기서 dist[목적지가] 더 작을 수 있으므로 Math.min을 사용한다.

이런식으로 1씩 증가해 가면서 주어진 Road 에 시작점과 move가 동일하다면 위에 설명처럼 dist[목적지]에 현 move 값에 .거리값을 더한 걸 ㄴ넣으면 된다.

 

예를 들면 입력 받은 데이터는

d

이렇게 들어온다.   0, 50, 10 이 처음으로 들어오는 데이터인데 move가 0일 때 r.start도 0 값이 들어온다. 그러면 당연히 dist[r.end] = dist[move]+r.cost 를 하면된다. 여기서 dist[r.end]]가 더 작은 경우도 있기에ㅐ Math.min을 건다.

그러면 dist[50] = dist[0]+10 이 된다. 첫 시작은 dist[0]=0 이므로 dist[50]=10 이 되는 것이다.

 

계속 이렇게 방문하는데 move와 r.start는 한참동안 같은 값이 나오지 않는다. 하지만 move는 계속 값을 1씩 증가해나간다.

move가 0이고 위에 결과를 일이키고 난뒤에는 index가 1일 것이다.

그러면 

dist[1] = Math.min(dist[move+1],dist[move]+1); 이 경우를 보면 아직 접근하지 않은 dist배열의 값들은 모두 10001 최댓값이다 결국 move와 start가 같지 않다면 dist[move+1] 값은 계속해서 1씩 더해져 나간다.

그러다 결국 move가 50이 된다면 

r.start와 만나게 된다. rmfjaus ektl

dist[r.end] = Math.min(dist[move]+r.cost,dist[r.end]) 를 실행한다.

dist[100] = Math.min(dist[50]+r.cost, dist[100]) 이 된다.

dist[50]은 이미 위에서 구한 지름길을 탄 값이다. 그럼 dist[100] 은 20이 된다.

 

이제 계쏙 이 값을 또 실행하면서 가는데

이렇게 가다가 start값이 같지 않으면 1씩 꼐속 더해가면서 move는 D에 도달하고 dist[D]에 결과값이 출력된다.

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

public class Main {

    static int dist[];
    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());   //고속도로의 길이

        List<Road> list = new ArrayList<>();
        dist = new int[10001];
        Arrays.fill(dist,10001);


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

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            if(D < end) continue;
            if(end - start <= cost) continue;
            list.add(new Road(start,end,cost));
        }
        Collections.sort(list, new Comparator<Road>() {
            @Override
            public int compare(Road o1, Road o2) {
                if(o1.start == o2.start) return o1.end - o2.end;
                return o1.start - o2.start;
            }
        });

        int index = 0;
        int move = 0;

        dist[0] = 0;

        while (move < D){
                if(index < list.size()){
                    Road r = list.get(index);
                    if(move == r.start){
                        dist[r.end] = Math.min(dist[move]+r.cost,dist[r.end]);
                        index++;
                    }else{
                        dist[move + 1] = Math.min(dist[move+1],dist[move]+1);
                        move++;
                    }
                }else{
                    dist[move + 1] = Math.min(dist[move+1],dist[move]+1);
                    move++;
                }
        }
        System.out.println(dist[D]);
    }
    static class Road{
        int start;
        int end;
        int cost;

        public Road(int start, int end,int cost){
                this.start = start;
                this.end =end;
                this.cost =cost;
        }
    }
}

 

참고

https://coder-in-war.tistory.com/entry/BOJ-JAVA1446-%EC%A7%80%EB%A6%84%EA%B8%B8

[ BOJ ][JAVA][1446] 지름길