[다익스트라] - G3_11779_최소 비용 구하기2

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

11779번: 최소비용 구하기 2

 

📌 - 처음 생각한 풀이

1. 도시와의 거리 = 시작지점을 제외하고는 전부 int 최댓값 초기화 , 이전도시 정보 배열 초기화
2. 인접리스트를 이용해서 리스트에 인접한 도시와 비용을 객체로 추가
3. bfs로 도시들을 방문
   - 비용이 최소일 때만 업데이트
   - 업데이트 할 때 그 비용은 dp배열에 저장하고 해당도시를 방문하기 전 도시를 result배열에 저장
4. result 배열을 역순으로 출력

 

처음 푼 코드는 답이 정확하게 나왔지만 메모리초과가 계속 발생해서 애를 먹었는데, 알고보니 bfs로 탐색을 할 때, 

백준에 있는 값으로 예시를 들면 1번 도시에서 2,3,4,5번에 전부 접근이 가능하기 때문에 큐에 2,3,4,5도시의 경로와 비용이 함께 들어가게된다. | (2,2),(3,3),(4,1),(5,10) |

 

 

해당 4번 도시를 방문해서 4번 도시의 인접 도시를 찾아서 계산할때 이미 5번 도시는 최소 경로인 4로 변경이 되지만 아직 큐에 (5,10)이 남아있는데 이 경우를 연산에 포함하지 않게 해야 메모리나 시간초과를 넘길 수 있다.

 

해당 코드를 구현하지 않으면 문제를 틀리게 된다.

 

 

🔥 - Java 코드

 

package 그래프탐색.G3_11779_최소비용구하기2;

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


class Line{
    int x;
    int cost;
    Line(int x , int cost){
        this.x=x;
        this.cost=cost;
    }
}

public class Main {
    public static int n,m;
    public static List<ArrayList<Line>> line;
    public static int[] dp,result;

    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());

        line = new ArrayList<>();
        dp = new int[n+1];
        result = new int[n+1];

        for (int i =0;i<n+1;i++){
            line.add(new ArrayList<Line>());
        }

        // 그래프에 인접도시 객체 추가
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a,b,cost;
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            cost = Integer.parseInt(st.nextToken());
            line.get(a).add(new Line(b,cost));
        }


        st = new StringTokenizer(br.readLine());
        int sC = Integer.parseInt(st.nextToken());
        int sA = Integer.parseInt(st.nextToken());

        // 거리 값 전부 최댓값으로 초기화
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[sC] = 0;
        bfs(sC); // 다익스트라 시작

        int count =0;

        System.out.println(dp[sA]);
        while(dp[sA] != 0){
            count++;
            sb.insert(0,sA + " ");
            sA = result[sA];
        }
        sb.insert(0,sC+ " ");
        System.out.println(count+1);
        System.out.println(sb);



    }


    public static void bfs(int start){
       Queue<Line> q = new LinkedList<>();
       q.add(new Line(start,0));

        while(!q.isEmpty()){
            Line x = q.poll();
            int cur = x.x;
            if(dp[cur] < x.cost){ // ******** 위쪽에서 예시를 든 핵심 코드가 이것이다. 이 코드가 없으면 메모리나 시간초과가 나온다.
                continue;           
            } // ***********
            for(int i =0;i<line.get(cur).size();i++){
                int nx =line.get(cur).get(i).x;
                int nc = line.get(cur).get(i).cost;

                if(dp[nx] > nc+dp[cur]){ //
                    dp[nx] = nc+dp[cur];
                    result[nx] = cur;
                    q.add(new Line(nx,dp[nx]));
                }

            }
        }
    }

}