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

문제링크

오늘은 다익스트라의 기본 버전에서 확장된 문제를 들고 왔다.

바로 최소경로의 길이 출력 및, 해당 경로를 출력하는 문제이다.

처음에는 아무생각없이 각 노드별로 다 경로를 구해놓고, 마지막에 해당 도착지의 경로를 출력해주면 되겠지 싶어서 아래와 같이 구현해보았다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    static class City implements Comparable<City> {
        int to;
        int cost;

        public City(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(City o) {
            return o.cost-this.cost;
        }
    }

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

        int start;
        int end;

        int vertex=Integer.parseInt(br.readLine());
        int edge = Integer.parseInt(br.readLine());

        int routeCost[] = new int[vertex+1];

        StringBuilder route[] = new StringBuilder[vertex+1];

        List<City> cityList[]= new List[vertex+1];

        for(int i=0; i<vertex+1; i++){
            routeCost[i] = 100000001;
            route[i] = new StringBuilder();
            cityList[i] = new ArrayList<>();
        }

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

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            cityList[from].add(new City(to, cost));
        }

        st=new StringTokenizer(br.readLine());

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

        //다익스트라 알고리즘

        PriorityQueue<City> pq = new PriorityQueue<>();
        routeCost[start] = 0;
        route[start].append(start);

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

        while (!pq.isEmpty()){
            City now = pq.poll();
            //System.out.println("현재 city : " + now.to);

            if(routeCost[now.to] < now.cost) continue;

            for(int i=0; i<cityList[now.to].size(); i++){
                City next = cityList[now.to].get(i);

                if(routeCost[now.to] + next.cost < routeCost[next.to]) {
                    routeCost[next.to] = routeCost[now.to] + next.cost;
                    pq.add(new City(next.to, routeCost[next.to]));
                    //값이 바뀐다면, route[now.to]에 next.to를 넣기
                    // route[now.to]에 새로운 StringBuilder 객체를 생성하고 값을 추가
                    route[next.to] = new StringBuilder(route[now.to].toString()).append(" "+next.to);
                }
            }
        }

        System.out.println(routeCost[end]);
        System.out.println(countNumbersInStringBuilder(route[end]));
        System.out.println(route[end]);

    }

    public static int countNumbersInStringBuilder(StringBuilder sb) {
        // 정규식을 이용하여 숫자를 찾습니다.
        Pattern pattern = Pattern.compile("\\d");
        Matcher matcher = pattern.matcher(sb);
        int count = 0;

        // 일치하는 숫자를 찾을 때마다 카운트를 증가시킵니다.
        while (matcher.find()) {
            count++;
        }

        return count;
    }
}

예제도 잘 나오길래 될 줄 알았다. 하지만..

바로 컷 당해버렸다.

그 후 이 방법으론 안될 것 같아 다음과 같은 방법을 시도해보았다.

풀이

경로 출력에 대한 것만 풀이하겠다.

1. 해당 경로의 이전 vertex를 저장할 배열을 만든다.
2. 경로 비용이 업데이트 될 시, 이전 vertex 역시 업데이트 된다.
3. 최소 경로를 모두 구하고 난 후, stack을 이용하여 경로를 역추적 한다.

즉 아래와 같다.

---

1. 해당 경로의 이전 vertex를 저장할 배열 생성

int preCity[] = new int[vertex+1];

---

2. 경로 비용이 업데이트 될 시, 이전 vertex 역시 업데이트

 while (!pq.isEmpty()) {
            City now = pq.poll();

            if(routeCost[now.to] < now.cost) continue;

            for(int i=0; i<cityList[now.to].size(); i++){
                City next = cityList[now.to].get(i);

                if(routeCost[now.to] + next.cost < routeCost[next.to]) {
                    routeCost[next.to] = routeCost[now.to] + next.cost;
                    pq.add(new City(next.to, routeCost[next.to]));
                    //값이 바뀐다면, 이전 city 기록해두기
                    preCity[next.to] = now.to;
                }
            }
        }

---

3. stack을 이용하여 경로 역추적

        //경로 역 추적
        int now = end;
        Stack<Integer> routeStack = new Stack<>();

        while (now!=0){
            routeStack.push(now);
            now = preCity[now];
        }

        //최소 경로의 수 저장
        int routeSize = routeStack.size();

        StringBuilder route = new StringBuilder();

        while (!routeStack.isEmpty()) {
            route.append(routeStack.pop()+" ");
        }

와! 경로 출력은 의외로 간단했다.