[백준/자바] 1956번: 운동

문제

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

풀이

• V개 마을, E개 도로로 구성된 도시
• 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다.
• 마을에서 출발하여 다시 출발지로 돌아오는 사이클이 있는지 찾아야 한다.
• 사이클을 이루는 도로의 길이합이 최소가 될 때 길이 출력

사이클을 이루는 경로의 최단 경로 탐색 문제입니다.
처음에 다익스트라로 풀었으나, 모든 출발지에서 다시 돌아오는 최단 경로가 존재하는지 찾아야 해서 다익스트라를 V번 실행해야 되더군요.
모든 경로에서의 최단 경로를 탐색할 거면 플로이드-워셜이 효율적일 것 같아 플로이드-워셜 알고리즘을 사용해 풀었습니다.

입력

		v = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		graph = new int[v+1][v+1];
		for (int i = 1; i <= v; i++) Arrays.fill(graph[i], INF);
		
		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());
			graph[a][b] = c;
		}

• v: 마을(노드)
• e: 도로(간선)
• graph: 마을과 마을(인덱스) 사이 도로 길이
• 최단 경로를 찾아야 하므로, 모든 도로의 길이를 최댓값으로 설정하였습니다.

모든 경로 길이 탐색(Floyd-Warshall)

	private static void floydWarshall() {
		for (int k = 1; k <= v; k++) {
			for (int i = 1; i <= v; i++) {
				for (int j = 1; j <= v; j++) {
					if (i == j) continue;
					if (graph[i][j] > graph[i][k] + graph[k][j]) {
						graph[i][j] = graph[i][k] + graph[k][j];
					}
				}
			}
		}
	}

• i -> j 경로가 k를 경유하는 것보다 길 때, 길이 업데이트

사이클을 이루는 도로 중 최솟값 탐색

	private static void printAnswer() {
		int answer = INF;
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				if (graph[i][j] == INF || graph[j][i] == INF) continue;
				answer = Math.min(answer, graph[i][j] + graph[j][i]);
			}
		}
		
		System.out.println(answer == INF ? -1 : answer);
	}

• i -> j와 j -> i 경로가 존재할 경우 최솟값을 갱신해 주었습니다.
• 만약 사이클을 이루는 경로가 없을 경우 -1을 출력하였습니다.

코드

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

public class Main {
	
	static int v, e;
	static int[][] graph;
	static final int INF = 1_000_000_000;
	
	private static void floydWarshall() {
		for (int k = 1; k <= v; k++) {
			for (int i = 1; i <= v; i++) {
				for (int j = 1; j <= v; j++) {
					if (i == j) continue;
					if (graph[i][j] > graph[i][k] + graph[k][j]) {
						graph[i][j] = graph[i][k] + graph[k][j];
					}
				}
			}
		}
	}
	
	private static void printAnswer() {
		int answer = INF;
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				if (graph[i][j] == INF || graph[j][i] == INF) continue;
				answer = Math.min(answer, graph[i][j] + graph[j][i]);
			}
		}
		
		System.out.println(answer == INF ? -1 : answer);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		v = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		graph = new int[v+1][v+1];
		for (int i = 1; i <= v; i++) Arrays.fill(graph[i], INF);
		
		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());
			graph[a][b] = c;
		}
		
		floydWarshall();
		printAnswer();
	}

}