[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)11779번, 최소비용 구하기 2

문제 링크

11779번: 최소비용 구하기 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

위 문제는 출발지점에서 목적지점까지 가는 비용이 최소인 경로를 구하는 문제이기 때문에 최단경로 알고리즘을 사용하였습니다.

최단경로는 시작 정점에서 목표 정점까지 최소의 비용으로 갈 수 있는 경로를 구하는 것입니다.

최단 경로를 구하는 알고리즘은 대표적으로 3개가 존재합니다.

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드 워셜 알고리즘

 

3가지 알고리즘은 문제를 해결할 때 사용하는 알고리즘만 설명하도록 하겠습니다.

최단 경로에서 가중치(비용)이 양수이고 단일 - 출발, 단일 - 도착이면 다익스트라 알고리즘으로 구현합니다.

다익스트라 알고리즘이란?

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

1. 출발 정점에서 인접한 정점으로 이동합니다.

2. 인접한 정점에서 가장 적은 가중치(거리)의 정점을 먼저 탐색합니다.

3. 이동을 할 때마다 이동한 거리가 현재 저장된 거리보다 작으면 변경합니다.

4. 위 과정을 반복이 끝나면 출발 정점에서 각 정점에 도착하는 최소 거리을 구할 수 있습니다.

 

글로는 잘 설명하지 못한 것 같아서 아래에 예제 문제를 풀면서 어떻게 진행되는지 자세히 보여드리겠습니다.

 

더 자세한 내용은 아래 링크를 통해 확인해주시기 바랍니다.

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 한 도시에서 다른 도시로 출발하는 버스이다. = 방향이 있는 간선이다.

2. 버스의 비용은 0보다 크거나 같다.

3. 출발점에서 도착점까지 최소비용, 경로, 방문 도시 개수를 출력해야 한다.

4. 출발 도시와 도착 도시도 방문 도시와 경로에 포함된다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

그래프의 값을 리스트에 저장하였다면 각 정점을 기준으로 BFS탐색으로 다익스트라 알고리즘을 구현하였습니다.

 

다익스트라 탐색하는 과정을 살펴보시려면 아래 링크 문제를 풀 때 어떻게 진행되는지 표현한 것을 참고해주시면 감사하겠습니다.

[백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)10217번, KCM Travel

 

이 문제에서는 최단 비용뿐만 아니라 지나가는 도시의 경로를 출력해야 합니다.

 

버스를 타고 이동할 때 이전 도시에 값들을 저장하는 배열을 만들었습니다.

 

만약 도시1 -> 도시2로 이동한다면

process[2] = 1이 저장되는 형식입니다.

 

다익스트라 알고리즘으로 최단 비용 경로를 구할 때 같이 배열을 구성합니다.

 

이후 경로를 출력할 때에는 LIFO(후입선출) 형식의 Stack을 이용하여 도착 지점부터 출발지점까지 가는 process에 값들을 역추적하면서 Stack에 도시 번호를 저장합니다.

 

Stack에 저장된 값들을 출력하여 경로를 표현할 수 있습니다.

 

Stack에 저장되었던 도시들은 최단 비용으로 갔을 때 들린 도시의 수로 표현할 수 있기 때문에 저장된 수만큼 결과로 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. n, m, 출발점, 도착점을 입력받습니다.

2. 도시별 버스의 경로를 graph에 저장합니다.

3. 다익스트라 알고리즘을 통하여 비용이 최소인 경로를 구합니다.

4. 최소 비용, Stack을 이용한 경로 및 방문 도시 개수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 버스의 이동경로를 나누어 graph에 저장하였습니다.
• BFS와 다익스트라 알고리즘를 이용하여 출발점에서 도착점에 가는 최단 비용을 구하는 cal함수를 실행하였습니다.
• BufferedWriter에 최단 비용을 저장하였습니다.
• Stack과 process[]을 이용하여 이동 경로와 방문 도시 개수를 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

• cal함수는 BFS와 다익스트라 알고리즘을 이용하여 process와 dist를 구성합니다. 

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

public class Main {
	//graph에 저장하는 노드 생성자
	static class node{
		int point, cost;	//다음 위치, 버스 비용

		public node(int point, int cost) {
			this.point = point;
			this.cost = cost;
		}
		public int getPoint() {
			return point;
		}

		public int getCost() {
			return cost;
		}
	}
	static int n,m;
	static ArrayList<ArrayList<node>> graph = new ArrayList<>();	//그래프 저장 리스트
	static int[] dist,process;		//최단 비용 저장 배열, 이전 도시 번호 저장 배열
    public static void main(String[] args) throws Exception {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-------입력값 저장 및 리스트 초기화--------
    	StringTokenizer st;
    	n = Integer.parseInt(br.readLine());
    	m = Integer.parseInt(br.readLine());
    	dist = new int[n+1];
    	process = new int[n+1];
    	for(int i=0;i<=n;i++)
    		graph.add(new ArrayList<>());
    	//그래프 값들 리스트에 저장
    	for(int i=0;i<m;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int s = Integer.parseInt(st.nextToken());
    		int e = Integer.parseInt(st.nextToken());
    		int cost = Integer.parseInt(st.nextToken());
    		graph.get(s).add(new node(e,cost));
    	}
    	st = new StringTokenizer(br.readLine()," ");
    	int start = Integer.parseInt(st.nextToken());
    	int end = Integer.parseInt(st.nextToken());
    	
    	cal(start,end);		//최단 비용의 경로 구하는 함수 실행
    	bw.write(dist[end] + "\n");		//최단 비용 BufferedWriter 저장
    	
    	Stack<Integer> stack = new Stack<Integer>();	//경로를 출력하기 위한 스택 선언
    	int count = 1;		//방문한 도시 개수
    	stack.push(end);	//도착 위치 Stack에 저장
        //경로 BufferedWriter 저장
    	while(process[end]!=0) {
    		stack.push(process[end]);
    		end = process[end];
    		count++;
    	}
    	bw.write(count + "\n");		//방문한 도시 개수 BufferedWriter 저장
    	while(!stack.isEmpty()) {
    		bw.write(stack.pop() + " ");	//경로 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //BFS를 이용한 다익스트라 알고리즘, 최단 비용 경로 구하는 함수
    static void cal(int s, int e) {
    	//비용에 따른 우선순위 큐
    	PriorityQueue<node> queue = new PriorityQueue<node>(new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				return o1.getCost()-o2.getCost();
			}
		});
    	queue.add(new node(s,0));	//출발 도시 큐에 저장
    	Arrays.fill(dist, Integer.MAX_VALUE);	//비용 배열 초기화
    	dist[s] = 0;		//출발 도시 비용 초기화
    	boolean[] visited = new boolean[n+1];	//도시 방문 여부 확인 배열 초기화
    	while(!queue.isEmpty()) {
    		node temp = queue.poll();
    		int point = temp.getPoint();
    		int cost = temp.getCost();
    		if(point == e) 		//목적지 도시 도착시
    			return;
    		
    		if(visited[point])		//이미 방문한 도시일 때
    			continue;
    		
    		visited[point] = true;
    		//해당 도시에서 버스로 갈 수 있는 도시에서 비용이 적은 도시 큐에 저장
    		for(node next : graph.get(point)) {
    			if(!visited[next.getPoint()] && cost + next.getCost() < dist[next.getPoint()]) {
    				dist[next.getPoint()] = cost + next.getCost();
    				queue.add(new node(next.getPoint(),dist[next.getPoint()]));
    				process[next.getPoint()] = point;
    			}
    		}
    	}
    	return;
    }
}