[BaekJoon] 1956 운동 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1956

2.  문제

요약

• V개의 마을과 E개의 도롤 구성된 도시가 있고, 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로입니다.
• 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있습니다.
• 도로를 따라 운동을 하기 위한 경로를 찾는데, 도로의 길이의 합이 최소가 되는 사이클을 찾으려고 합니다.
• 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 문제입니다.
• 두 마을을 왕복하는 경우도 사이클에 포함됩니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 400보다 작거나 같은 V와 0보다 크거나 같고 V * (V - 1)보다 작거나 같은 E가 주어지고 두 번째 줄부터 E개의 줄에는 각각 세개의 정수 a, b, c가 주어집니다. 이는 a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 뜻입니다.
  • c는 10,000 이하의 자연수입니다.
  • (a, b) 쌍이 같은 도로가 여러 번 주어지지 않습니다.
• 출력: 첫 번째 줄에 최소 사이클의 도로 길이의 합을 출력합니다. 만약 운동 경로를 찾는 것이 불가능하다면 -1을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int V, E;
	static int[][] distance;
	static void input() {
		Reader scanner = new Reader();
		V = scanner.nextInt();
		E = scanner.nextInt();
		distance = new int[V + 1][V + 1];
		for(int row = 0; row <= V; row++) {
			for(int col = 0; col <= V; col++) {
				if(row != col) distance[row][col] = Integer.MAX_VALUE;
			}
		}
		for(int edge = 0; edge < E; edge++) {
			int start = scanner.nextInt(), end = scanner.nextInt(), weight = scanner.nextInt();
			distance[start][end] = weight;
		}
	}
	
	static void solution() {
		floydWarshall();
		int min = Integer.MAX_VALUE;
		for(int row = 1; row <= V; row++) {
			for(int col = 1; col <= V; col++) {
				if(row == col) continue;
				if(distance[row][col] != Integer.MAX_VALUE && distance[col][row] != Integer.MAX_VALUE)
					min = Math.min(min, distance[row][col] + distance[col][row]);
			}
		}
		System.out.println(min == Integer.MAX_VALUE ? -1 : min);
	}
	
	static void floydWarshall() {
		for(int node = 1; node <= V; node++) {
			for(int node1 = 1; node1 <= V; node1++) {
				for(int node2 = 1; node2 <= V; node2++) {
					if(node1 == node2) continue;
					if(distance[node1][node] == Integer.MAX_VALUE || distance[node][node2] == Integer.MAX_VALUE) continue;
					if(distance[node1][node2] > distance[node1][node] + distance[node][node2])
						distance[node1][node2] = distance[node1][node] + distance[node][node2];
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 플로이드-워셜 알고리즘은 가능한 모든 정점에 대해 최단거리를 구하는 알고리즘인데, 음의 사이클이 발생하지 않는다면 최단 거리를 구할 수 있습니다.
• 문제에서 도로의 거리는 10,000 이하의 자연수라고 했기 때문에 음의 사이클이 발생하지 않으므로 해당 알고리즘을 이용하여 문제를 해결할 수 있습니다.
• 플로이드-워셜 알고리즘은 아래와 같이 동작합니다.
  • 만약 노드 s에서 노드 e로 간다고 가정하면, s와 e 사이의 노드 m에 대해 s부터 m까지의 최단거리와 m부터 e까지의 최단 거리를 이용합니다.
  • 각 노드에서 다른 노드로의 최단거리를 배열에 저장하기 때문에 2차원 배열 distance에 가능한 모든 정점에 대한 최단거리를 저장합니다.
  • 처음에는 어떠한 노드 s에서 어떠한 노드 e로 간선을 통해 연결되어 있다면 해당 간선의 가중치로 distance[s][e]의 값을 설정하고 그렇지 않다면 INF로 값을 설정합니다.
  • 그 이후에는 시작 노드 s, 도착 노드 e, 중간 노드 m을 잡아 distance[s][e]의 값을 Math.min(distance[s][e], distance[s][m] + distance[m][e])로 설정합니다.
  • 모든 노드에 대해 위 작업을 시행하면 가능한 모든 노드에 대한 최단거리를 구할 수 있습니다.
• 플로이드-워셜 알고리즘을 이용하여 가능한 모든 노드에 대한 최단거리를 구합니다.
• 그렇게 구한 최단거리가 2차원 배열 distance에 존재할텐데, 만약 임의의 두 노드 s와 e에 대해서 distance[s][e]가 INF가 아니고 distance[e][s]가 INF가 아니라면 s에서 e로도 갈 수 있고 e에서 s로도 갈 수 있다는 뜻이 되기 때문에 두 노드 s와 e에 대해서 사이클이 발생했다고 볼 수 있습니다.
• 그렇기 때문에 그러한 두 노드를 찾아 distance[s][e] + distance[e][s] 값을 구하고 그 중 최소값을 구합니다.
• 만약 그러한 두 노드가 없다면 -1을 출력합니다.