백준 11779 (최소비용 구하기 2) - java

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

11779번: 최소비용 구하기 2

'최소비용 구하기'와 비교하여 추가로 구현해야 할 사항이 있다.

• 출발지부터 도착지까지의 경로 (정점들을 공백으로 구분)
• 경로까지 지나온 정점의 개수(출발지 , 목적지 포함)

경로를 표현하는 방법

• 경로를 표현하는 방법은 간단하다. 모든 정점에 대하여 방금 전에 지나온 정점을 저장하는 past[] 배열을 사용하면 된다.

for (Edge next : graph.get(cur.v)) {
     if (dis[cur.v] + next.c < dis[next.v]) {
           dis[next.v] = dis[cur.v] + next.c;
           pq.add(new Edge(next.v, dis[next.v]));
           past[next.v] = cur.v; // 다음 정점에 그 바로 전의 정점을 저장
       }
}

위와 같이 작성할 경우 도착지에서 역으로 past[] 배열을 거슬러 올라가면서 (출발지 값이 나올때까지) 경로를 쉽게 구할 수 있다.

 

경로의 정점 개수

        int count = 0;

        ArrayList<Integer> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int tmp = end;

        while(tmp!=0)
        {
            result.add(tmp);
            tmp = past[tmp];
            count = count + 1;
        }

        for(int i=result.size()-1;i>=0;i--)
        {
            sb.append(result.get(i)+" ");
        }

        System.out.println(count);
        System.out.println(sb);

다음은 내가 작성한 경로를 뽑아내는 과정이다. 그 과정에서 개수를 세는 한 줄만 추가해주면 된다.

 

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
        for(int i=0;i<=n;i++)
        {
            graph.add(new ArrayList<>());
        }

        for(int i=1;i<=m;i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");

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

            graph.get(start).add(new Edge(end,cost));
        }

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());

        search(graph,x,y);
        br.close();
    }

    static void search(ArrayList<ArrayList<Edge>> graph,int start,int end) {
        boolean[] visit = new boolean[n + 1];
        int[] dis = new int[n + 1];
        int[] past = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dis[i] = Integer.MAX_VALUE;
        }
        dis[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(
                (x, y) -> x.c - y.c
        );

        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();

            if (visit[cur.v])
                continue;

            visit[cur.v] = true;

            for (Edge next : graph.get(cur.v)) {
                if (dis[cur.v] + next.c < dis[next.v]) {
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Edge(next.v, dis[next.v]));
                    past[next.v] = cur.v;
                }
            }
        }

        System.out.println(dis[end]);

        int count = 0;

        ArrayList<Integer> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int tmp = end;

        while(tmp!=0)
        {
            result.add(tmp);
            tmp = past[tmp];
            count = count + 1;
        }

        for(int i=result.size()-1;i>=0;i--)
        {
            sb.append(result.get(i)+" ");
        }

        System.out.println(count);
        System.out.println(sb);

    }
}
class Edge
{
    int v;
    int c;

    Edge(int v,int c)
    {
        this.v = v;
        this.c = c;
    }
}