[백준] 단계별로 풀어보기(단계:25, 최단 경로,JAVA)11657번, 타임머신

문제 링크

11657번: 타임머신

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

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

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

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

 

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

최단 경로에서 가중치(비용)이 음수이면 벨만-포드 알고리즘으로 구현합니다.

 

벨만-포드 알고리즘이란?

1. 출발 정점을 시작으로 모든 간선의 이동을 탐색합니다.

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

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

4. 가중치가 음수가 들어가서 음수 싸이클이 발생할 수 있으므로 싸이클 발생을 확인해주어야 합니다.

 

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

 

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

벨먼-포드 알고리즘 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

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

2. 방향이 있는 간선이다.

3. 정점 1을 출발 정점으로 2~N까지의 최단 경로를 출력해야 한다.

4. 정점에 도착하지 못하면 -1을 출력한다.

5. 음수 사이클이 존재하면 -1을 출력한다.

 

벨만 - 포드 알고리즘은 모든 노드를 확인하기 때문에 정점 N - 1번을 반복한다.

하지만 음수 사이클이 있으면 최단 경로가 무한히 감소할 수 있습니다.

그래서 음수 사이클을 확인하는 방법은 N - 1번만 반복하는 것이 아닌 N번을 반복하여

마지막 N번일 때에도 최단 경로가 감소한다면 음수 사이클이 돌고 있다고 판단할 수 있습니다.

 

저는 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탐색으로 벨만-포드 알고리즘을 구현하였습니다.

 

예제 입력1의 그래프와 표로 확인하며 보여드리겠습니다.

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

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

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

 

벨만-포드로 그래프를 탐색하는 과정을 살펴보겠습니다.

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

1	2	3
0	INF	INF

 

1. 출발 정점 1에서 노드를 탐색합니다.

노드를 탐색합니다.

1	2	3
0	4	3

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

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

 

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

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

 

2. 출발 정점과 인접했던 정점 2에서 노드를 탐색합니다.

노드를 탐색합니다.

1	2	3
0	4	3

현재 정점의 거리 : 4, 간선의 거리 : -1 = 4 + (-1) = 3

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

3 == 3이므로 변경되지 않았습니다.

 

3. N-1번을 탐색하였기 때문에 이제는 음수 사이클이 존재하는지 확인합니다.

노드를 탐색합니다.

1	2	3
0	4	3

현재 정점의 거리 : 3, 간선의 거리 : -2 = 3 + (-2) = 1

원래 표의 정점 1의 거리는 0으로

1 > 0이므로 변경되지 않았습니다.

 

4. N번째 확인에서 변경되지 않았기 때문에 음수 사이클이 존재하지 않는 그래프로 판정되었습니다.

 

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

1	2	3
0	4	3

 

1 -> 2 = 최단 거리 = 4

1 -> 3 = 최단 거리 = 3

 

4 3이 결과로 출력됩니다.!

 

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

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

2. 벨만 - 포드 알고리즘을 통해 N-1번 반복하여 정점 1부터 출발하는 각 정점의 최단 거리를 구합니다.

3. 마지막 N번째에 최단 거리가 변경되면 음수 싸이클이 존재한다고 판정한다.

4. 음수 싸이클이 존재하면 -1을 출력하고 아니면 각 정점의 최단거리를 출력합니다.

5. 음수 싸이클이 존재하지 않지만 해당 정점을 가지 못한다면 -1을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 그래프에 대한 정보를 저장하였습니다.
• 그래프에 사용할 point(정점), cost(거리)를 저장하는 city 생성자를 만들었습니다.
• 그래프에 내용 저장할 ArrayList<ArrayList<Integer>> graph를 만들었습니다.
• 반복문으로 최단 경로(벨만-포드)를 구하는 shortestPath 함수를 만들었습니다.
• 정점 1부터 시작하는 각 정점의 최단 경로를 구하였습니다.
• BufferedWriter에 음수 싸이클 존재하면 -1, 음수 싸이클 존재하지 않으면 최단 경로 저장
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• shortestPath은 distance[], graph를 통해 인접한 정점을 탐색하였습니다.
• shortestPath는 벨만-포드 알고리즘과 반복문을 이용하여 작성하였습니다.
• shortestPath는 탐색을 N번 반복하여 음수 싸이클 존재 유무를 확인하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//큐에 사용할 생성자
	public static class city{
		int point, cost;
		public city(int point, int cost) {
			this.point = point;
			this.cost = cost;
		}
		public int getPoint() {
			return point;
		}

		public int getCost() {
			return cost;
		}
	}
	public static int N,M;	//정점의 수, 간선의 수
	public static ArrayList<ArrayList<city>> graph = new ArrayList<>();	//그래프 값
	public static long[] distance;	//최단 경로 저장 배열
    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());
    	M = Integer.parseInt(st.nextToken());
    	distance = new long[N+1];
    	
    	for(int i=0;i<N+1;i++)
    		graph.add(new ArrayList<>());
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		int A = Integer.parseInt(st.nextToken());
    		int B = Integer.parseInt(st.nextToken());
    		int C = Integer.parseInt(st.nextToken());
    		graph.get(A).add(new city(B,C));
    	}
    	if(shortestPath(1))		//음수 싸이클 존재 시
    		bw.write("-1\n");
    	else {		//음수 싸이클 존재하지 않을 때
    		for(int i=2;i<=N;i++) {
    			if(distance[i]==Integer.MAX_VALUE) 	//해당 정점 도착 못할 시
    				bw.write("-1\n");
    			else		//해당 정점 도착 시
    		    	bw.write(distance[i] + "\n");
    		}
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //벨만 - 포드 알고리즘을 반복문으로 구현한 함수
    //반환 값 True이면 음수 싸이클 존재, False이면 음수 싸이클 없음
    public static boolean shortestPath(int start) {
    	//최단 경로 초기화
    	Arrays.fill(distance, Integer.MAX_VALUE);
    	distance[start] = 0;
    	for(int i=0;i<N;i++) {	//음수 사이클 확인하기 위해 N번 반복
        	for(int j=1;j<=N;j++) {
        		for(city value : graph.get(j)) {
        			if(distance[j] == Integer.MAX_VALUE)	//해당 정점 아직 도착 안햇을 때
        				break;
        			if(distance[value.getPoint()] > distance[j] + value.getCost()) {
        				distance[value.getPoint()] = distance[j] + value.getCost();
        				if(i==N-1)		//N-1번일 때 최단 경로가 변경되었을 때
        					return true;		//음수 싸이클 존재 반환
        			}
        		}
        	}
    	}
    	return false;		//음수 싸이클 없음 반환
    }
}