[백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)1504번, 특정한 최단 경로

문제 링크

1504번: 특정한 최단 경로

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

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

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

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

 

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

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

 

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

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

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

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

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

 

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

 

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

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

 

이 문제에 핵심은

1. 입력값으로 주는 내용은 모두 그래프의 내용입니다.

2. 시작점에서 v1과 v2를 지나서 N까지 도착하는 최단 거리를 구해야합니다.

3. 시작점에서 v1과 v2를 지나서 도착점까지 도착못하면 -1를 출력합니다.

4. 방향성이 없는 그래프가 주어진다. = 방향이 없는 양방향 간선이다.

 

저는 BFS(너비우선탐색)와 다익스트라 알고리즘을 사용하여 해결하였습니다.

그래프에 대한 내용을 정의하기 위해 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탐색으로 다익스트라 알고리즘을 구현하였습니다.

 

처음이 이 문제를 접근할 때 생성자 node에 check를 포함시켜서 v1과 v2를 지나면 true로 바꾸어 정점 N에 도착했을 때 check가 true이면 최소 거리를 구하도록 하려고 진행하였습니다.

위 방법으로 1시간 정도 머리를 굴리다가 훨씬 간단하게 구할 수 있을 것 같은 방법을 찾았습니다.

정점 1에서 v1과 v2를 지나서 N까지 가는 방법은

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

이 두 가지 방법을 따로 최단 경로(다익스트라)를 구해서 더해준다면 1 -> N까지 가는 최단 경로를 쉽게 구할 수 있게 되었습니다.

 

만약 N = 7, v1 = 2, v2 = 5이면

1 -> v1까지 가는 최단 거리

v1 -> v2까지 가는 최단 거리

v2 -> N까지 가는 최단 거리

모두 더하면 1 -> v1 -> v2 -> N까지 가는 최단 경로를 구할 수 있습니다.

 

1 -> v2까지 가는 최단 거리

v2 -> v1까지 가는 최단 거리

v1 -> N까지 가는 최단 거리

모두 더하면 1-> v2 -> v1 -> N까지 가는 최단 경로를 구할 수 있습니다.

 

이후 두 경우의 최단 경로를 비교하여 더 작은 최단 경로를 결과로 출력하면 됩니다.

 

예제 입력1에서 첫 번째 테스트케이스의 그래프를 표로 확인하며 보여드리겠습니다.

아래는 예제로 주어진 그래프입니다.

그래프의 내용이 저장된 ArrayList<ArrayList<>>의 해당하는 표

정점
1	2(거리 : 3)	3(거리 : 5)	4(거리 : 4)
2	1(거리 : 3)	3(거리 : 3)	4(거리 : 5)
3	1(거리 : 5)	2(거리 : 3)	4(거리 : 1)
4	1(거리 : 4)	2(거리 : 5)	3(거리 : 1)

최단 경로를 구해야 하는 경우는

1->v1, v1->v2, v2->N의 3가지 경우

1->v2, v2->v1, v1->N의 3가지 경우

BFS를 진행하는 과정은 1->v1을 구하는 과정만 보여줄 것입니다.

출발 정점1에서 각 지점의 최소 거리을 정리한 표(자신 거리는 = 0, 아직 가보지 않은 곳은 INF(무한대)로 표현)

1	2	3	4
0	INF	INF	INF

 

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

정점 2로 이동합니다.

1	2	3	4
0	3	INF	INF

원래 표의 정점 2의 거리는 INF로써

3 < INF이므로 INF가 3으로 변경되었습니다.

 

정점 3으로 이동합니다.

1	2	3	4
0	3	5	INF

원래 표의 정점 3의 거리는 INF로써

5 < INF이므로 INF가 5으로 변경되었습니다.

 

정점 4로 이동합니다.

 

1	2	3	4
0	3	5	4

2. 간선에 거리가 적었던 정점 2에서 인접한 정점을 탐색합니다.

정점 3으로 이동합니다.

1	2	3	4
0	3	5	4

현재 정점의 거리 : 3, 간선의 거리 : 3 = 3 + 3 = 6

원래 표의 정점 3의 거리는 5으로

6 > 5이므로 변경되지 않았습니다.

 

정점 4으로 이동합니다.

1	2	3	4
0	3	5	4

현재 정점의 거리 : 3, 간선의 거리 : 5 = 3 + 5 = 8

원래 표의 정점 4의 거리가 4으로

8 > 4이므로 변경되지 않았습니다.

 

3. 다음 정점 1의 인접하여 거리가 적은 정점 3을 탐색합니다.

정점 4로 이동합니다.

1	2	3	4
0	3	5	4

현재 정점의 거리 : 5, 간선의 거리 : 1 = 5 + 1 = 6

원래 표의 정점 4의 거리는 4으로

6 > 4이므로 변경되지 않았습니다.

 

4. 더 이상 탐색할 수 있는 간선이 존재하지 않기 때문에 탐색을 종료합니다!

 

현재 최소 거리가 저장된 표를 순서대로 결과로 출력합니다.

1	2	3	4
0	3	5	4

v1 = 2, v2 = 3, N = 4이고구해야하는 최단 경로를 모두 구하면

1 -> v1(2)  = {0, 3, 5, 4} = 1에서 2으로 가는 최단경로 = 3

v1(2) -> v2(3) = {3, 0, 3, 4} = 2에서 3으로 가는 최단경로 = 3

v2(3) -> N(4) = {5, 3, 0, 1} = 3에서 4으로 가는 최단경로 = 1

 

1 -> v2(3) = {0, 3, 5, 4} = 1에서 3으로 가는 최단경로 = 5

v2(3) -> v1(2) = {5, 3, 0, 1} = 3에서 2으로 가는 최단경로 = 3

v1(2) -> N(4) = {3, 0, 3, 4} = 2에서 4으로 가는 최단경로 = 4

 

1 -> v1 -> v2 -> N = 3 + 3 + 1 = 7

1 -> v2 -> v1 -> N = 5 + 3 + 4 = 12

 

 7 < 12이기 때문에 1 -> v1 -> v2 -> N인 경우가 최단 거리로 결과는 7이 출력됩니다.

 

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

1. 그래프에 대한 정보를 ArrayList<ArrayList<node>>에 저장합니다.

2. 1 -> v1 -> v2 -> N, 1 -> v2 -> v1 -> N인 경우를 다익스트라로 탐색합니다.

3. 두 경우 중 작은 최단 거리를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 그래프에 대한 정보를 저장하였습니다.
• 그래프에 사용할 point(정점), cost(거리)를 저장하는 node 생성자를 만들었습니다.
• 그래프에 내용 저장할 ArrayList<ArrayList<Integer>> graph를 만들었습니다.
• BFS로 최단 경로(다익스트라)를 구하는 shortestPath 함수를 만들었습니다.
• 위에서 설명한 두 가지 경우의 최단 경로를 구하였습니다.
• BufferedWriter에 정점 N에 도착 못하면 -1, 도착하면 두 경우 중에 최단 거리를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• shortestPath은 distance[], graph와 PriorityQueue를 통해 인접한 정점을 탐색하였습니다.
• shortestPath는 다익스트라 알고리즘과 BFS를 구조를 이용하여 작성하였습니다.
• shortestPath는 목적지에 대한 최단 거리를 반환하도록 하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//목적지와 가중치를 저장하는 생성자
	public 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;
		}
	}
	public static int N,E;
	public static int[] distance;		//최단 거리 저장하는 배열
	public static ArrayList<ArrayList<node>> graph = new ArrayList<>();	//그래프 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 리스트 초기화--------
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<N+1;i++) 	//리스트 초기화
    		graph.add(new ArrayList<>());
    	//그래프 값 저장
    	for(int i=0;i<E;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int c = Integer.parseInt(st.nextToken());
    		//양방향으로 a -> b, b -> a 모두 저장
    		graph.get(a).add(new node(b,c));
    		graph.get(b).add(new node(a,c));
    	}
    	//필수로 지나는 정점 저장
    	st = new StringTokenizer(br.readLine()," ");
    	int v1 = Integer.parseInt(st.nextToken());
    	int v2 = Integer.parseInt(st.nextToken());
    
    	distance = new int[N+1];
    	
        //1 -> v1 -> v2 -> N 최단 경로 구하기
    	long result = shortestPath(1, v1);
    	result += shortestPath(v1, v2);
    	result += shortestPath(v2, N);
    	//1 -> v2 -> v1 -> N 최단 경로 구하기
    	long temp = shortestPath(1, v2);
    	temp += shortestPath(v2, v1);
    	temp += shortestPath(v1, N);
    	
    	result = Math.min(result, temp);	//두 경우중 작은 값 결과로 저장
    	if(result >= Integer.MAX_VALUE)
    		bw.write("-1\n");	//두 경우 둘다 목적지 도착 못할 경우
    	else
    		bw.write(result + "\n");		//도착했으며 더 작은 최단 경로
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //--------BFS와 다익스트라를 이용한 최단 경로 구하는 함수--------
    public static int shortestPath(int start, int end) {
    	Arrays.fill(distance, Integer.MAX_VALUE);
    	distance[start] = 0;		//시작 정점 거리 0으로 초기화
         /*
        우선순위 큐를 사용해서 현재 정점들에서 거리가 가장 적은 정점을
        바로 poll()을 할 수 있도록 거리가 작은 순으로 Queue에 저장되도록
        Comparator를 설정해주었습니다.
        */
    	PriorityQueue<node> queue = new PriorityQueue<node>(new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				return o1.cost-o2.cost;
			}
		});
    	queue.add(new node(start,0));
    	while(!queue.isEmpty()) {
    		node temp = queue.poll();
    		int point = temp.getPoint();
    		int cost = temp.getCost();
            /*
            정점에 도착했을 때 최소 거리보다 크면
            해당 정점에 간선 어디를 가도 최소 거리가 되지 않기 때문에
            해당 탐색을 그대로 넘어갔습니다.
            */
    		if(distance[point] < cost)
    			continue;
    		for(node value : graph.get(point)) {
            		//더 작은 경로 찾을 때
        		if(distance[value.getPoint()] > value.getCost() + cost) {
        			distance[value.getPoint()] = value.getCost() + cost;
        			queue.add(new node(value.getPoint(),value.getCost() + cost));
        		}
    		}
    	}
    	return distance[end];	//목적지 최단경로 반환
    }
}