[BOJ] 백준 11779번: 최소비용 구하기 2 (JAVA)

 

 

- 문제 출처 : https://www.acmicpc.net/problem/11779

---

1. 생각

다익스트라 기본 문제를 풀어보기 위해 문제를 선택하였다.

 

n개의 도시에 m개의 버스가 있고, A번 도시에서 B번 도시로 가는 최소비용과 경로를 출력하는 문제이다.

(1 <= n <= 1000, 1 <= m <= 100000)

 

우선은 클래스를 하나 만들어서 목적지와 현재까지의 가중치를 저장할 변수를 담으려고 했고,

그 가중치를 기반으로 PriorityQueue에 넣어 다익스트라에 적용하는 것으로 생각했다.

 

기존 다른 다익스트라 문제와 다른 점은, 출력 부분에 보면

1) 최소비용 / 2) 최소비용 경로 포함 도시 개수 / 3) 최소 비용 경로 도시 순서

 

이렇게 구해야하는 것이 3개나 있었다.

최소비용은 기존 처럼 min값을 누적해가면서 구하면 되는데,

나머지는 생각이 좀 필요해보였다.

 

2. 난관 & 해결방법

경로를 구하는 방법을 몰라서 많이 헤맸는데, 역추적 방식을 이용하라는 힌트를 보고 해결 방향을 잡았다.

 

for (Bus b : BusList.get(now))
{
    int to = b.to;
    int weight = b.weight;


    if (!visited[to] && minCost[to] > total + weight)
    {
        minCost[to] = total + weight;
        parents[to] = now;
        pq.add(new Bus(to, minCost[to]));
    }
}

 

다익스트라 for문이 들어가는 파트에서,

parents 라는 int[ ] 배열을 각각 대입해줄 것인데, 이 배열의 역할은

최소 비용일 때의 이전 도시가 어디인지 저장해두는 배열이다.

 

현재 목적지 to의 이전 도시 now를 parents[to] 에 저장하는데, 이러면 그 도시에 도달하기 위한

가장 최소 비용의 경로가 저장된다고 볼 수 있다.

 

Stack <Integer> path = new Stack<>();
int cur = endPoint;
while (cur != 0)
{
    path.push(cur);
    cur = parents[cur];
    if (cur == startPoint)
    {
        path.push(cur);
        break;
    }
}
System.out.println(path.size());
while (!path.isEmpty())
{
    int p = path.pop();
    System.out.print(p + " ");
}

 

그 저장해둔 parents[] 배열을 어떻게 사용해야 '시작도시부터 목적지 도시 까지의 경로'를 출력 시킬 수 있을까?

 

바로 Stack 자료구조를 이용한, '역추적' 방식이다.

 

역추적이면 말 그대로, 뒤에서 부터 추적하는 것인데,

그럼 여기서는 '목적지 도시' 부터 '시작 도시'로 추적을 진행하는 것으로 생각하면 된다.

 

그래서 cur 변수에 endPoint를 저장하고 시작하며,

Stack에 cur를 push하고, cur를 parents[cur] 로 지정하여

이전 경로로 이동한 뒤 다시 while문을 반복한다.

 

그러다 시작 지점에 도달하면 break 해준다.

 

이후, Stack에 쌓인 값들을 pop()하며 출력해주면,

시작 지점부터 차례대로 경로의 도시들이 하나씩 나오게 된다.

 

 

 

이외에 다른 코드들은 일반적인 다익스트라 방식과 동일하게 풀었다!

 

도시를 잇는 간선들을 리스트로 저장하고, 각 도시별로 최소비용을 INF로 지정한 뒤,

우선순위 큐에 시작지점을 넣고, 간선+지금까지의 비용이 그 저장된 최소비용보다 적으면 갱신해주며,

그때마다 우선순위 큐에 넣어 지점별로 최소비용들일 때 방문하도록 세팅해주면 다익스트라가 완료 된다.

 

3. 코드 및 결론

[ 전체 코드 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int M;
	static int startPoint;
	static int endPoint;
	static final int INF = 987654321;
	static List <List<Bus>> BusList;
	
	static class Bus implements Comparable<Bus> {
		int to;
		int weight;
		
		public Bus(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Bus o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
	
	static void dijkstra() {
		int[] minCost = new int[N + 1];
		int[] parents = new int[N + 1];
		boolean[] visited = new boolean[N + 1];
		PriorityQueue<Bus> pq = new PriorityQueue<>();
		
		for (int i = 1; i <= N; ++i)
		{
			minCost[i] = INF;
		}
		
		minCost[startPoint] = 0;
		pq.add(new Bus(startPoint, minCost[startPoint]));

		while (!pq.isEmpty())
		{
			Bus pollData = pq.poll();
			int now = pollData.to;
			int total = pollData.weight;
			
			if (visited[now])
				continue;
			
			visited[now] = true;
			
			if (now == endPoint)
			{
				System.out.println(total);
				
				Stack <Integer> path = new Stack<>();
				int cur = endPoint;
				while (cur != 0)
				{
					path.push(cur);
					cur = parents[cur];
					if (cur == startPoint)
					{
						path.push(cur);
						break;
					}
				}
				System.out.println(path.size());
				while (!path.isEmpty())
				{
					int p = path.pop();
					System.out.print(p + " ");
				}
				return ;
			}
			
			for (Bus b : BusList.get(now))
			{
				int to = b.to;
				int weight = b.weight;
				
				
				if (!visited[to] && minCost[to] > total + weight)
				{
					minCost[to] = total + weight;
					parents[to] = now;
					pq.add(new Bus(to, minCost[to]));
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		BusList = new ArrayList<>();
		for (int n = 0; n <= N; ++n)
		{
			BusList.add(new ArrayList<>());
		}
		
		for (int m = 0; m < M; ++m)
		{
			st = new StringTokenizer(br.readLine());
			
			int s = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			
			BusList.get(s).add(new Bus(t, w));
		}
		
		st = new StringTokenizer(br.readLine());
		startPoint = Integer.parseInt(st.nextToken());
		endPoint = Integer.parseInt(st.nextToken());
		
		dijkstra();
	}
}

 

[ 결론 ]

 

오랜만에 다익스트라를 풀었더니 머리에서 떠오르지가 않았다.

확실히 다양하게 문제들을 복습하는 쪽이 좋을 것 같다.

 

그리고, 역추적 방식을 이용한 것은 처음인데,

다익스트라나 경로 관련된 문제에서는 역추적을 활용하는 것이 꽤나 괜찮을 듯 하다.

여기서 Stack을 활용한 점에서 확실히 자료구조들을 자유자재로 쓸 줄 알면 

알고리즘을 정확히 몰라도 자연스럽게 구현이 될 수 있겠다 싶다.

 

결론은 자료구조와 알고리즘을 모두 자주 복습하자!