[백준] 1956번 운동

문제정리

1. 사이클을 이루는 도로의 길이의 합이 최소가 되도록 한다.

2. 각 마을(1~V) 어디에서 시작해도 상관없다.(시작한 마을로 다시 돌아와야한다.)

풀이방법

플로이드 워셜 알고리즘

소스

package boj;

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

public class BOJ_1956_운동 {
	
	static BufferedReader br;
	static StringTokenizer st;
	static int V; //마을 갯수
	static int E; //도로 갯수
	static int[][] arr;
	static int minDistance = Integer.MAX_VALUE;
	static boolean[] visitCheck;
	
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		arr = new int[V+1][V+1];
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int fromPoint = Integer.parseInt(st.nextToken());
			int ToPoint = Integer.parseInt(st.nextToken());
			int distance = Integer.parseInt(st.nextToken());
			arr[fromPoint][ToPoint] = distance;
		}
		
		for(int i=1; i<V; i++) {
			visitCheck = new boolean[V+1];
			dfs(i,0,i);
		}
		
		if(minDistance == Integer.MAX_VALUE) {
			minDistance = -1;
		}
		System.out.println(minDistance);
	}
	
	public static void dfs(int from, int curr, int destination){
		
		// 계산도중 거리가 최소거리보다 길어도 멈춤
		if(minDistance < curr) {
			return;
		}
		
		// 다시 시작점으로 돌아왔을때 지금까지 확인한 거리와 비교
		if(curr !=0 && from == destination) {
			if(minDistance > curr) {
				minDistance = curr;
				return;
			}
		}
		
		for(int i=1; i<=V; i++) {
			if(arr[from][i] != 0 && !visitCheck[i]) {
				visitCheck[i] = true; 
				dfs(i, curr+arr[from][i], destination);
				visitCheck[i] = false;
			}
		}
	}
}

위처럼 풀었을때는 1964ms초가 걸린다.

그런데 플로이드 워셜 알고리즘을 사용했을때는,,

package boj;

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

public class BOJ_1956_운동_재 {
	
	static BufferedReader br;
	static StringTokenizer st;
	static int V; //마을 갯수
	static int E; //도로 갯수
	static int[][] arr;
	static int minDistance = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		int INF = Integer.MAX_VALUE;
		
		arr = new int[V+1][V+1];
		
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int fromPoint = Integer.parseInt(st.nextToken());
			int ToPoint = Integer.parseInt(st.nextToken());
			int distance = Integer.parseInt(st.nextToken());
			arr[fromPoint][ToPoint] = distance;
		}
		
		//길이가 주어지지 않은 값은 10000000(큰값)으로 초기화
		for(int i=1; i<=V; i++) {
			for(int j=1; j<=V; j++) {
				if(arr[i][j]==0) {
					arr[i][j] = INF;
				}
			}
		}
		
		for(int a=1; a<=V; a++) { // a는 시작점
			for(int b=1; b<=V; b++) { //b는 도착점
				
				//시작점과 도착점이 같다면 넘어간다.
				if(a == b) continue; 
				
				//k는 거쳐가는 지점
				for(int k=1; k<=V; k++) { 
					if(a != k && b != k && INF != arr[a][k] && INF != arr[k][b]) {
						arr[a][b] = Math.min(arr[a][b], arr[a][k]+arr[k][b]);
					}
				}
			}
		}
		
		for(int a=1; a<=V; a++) { // a는 시작점
			for(int b=1; b<=V; b++) { //b는 도착점
				if(a != b && arr[a][b]!=INF && arr[b][a]!=INF) { 
					minDistance = Math.min(arr[a][b]+arr[b][a],minDistance);
				}
			}
		}
		
		if(minDistance == Integer.MAX_VALUE) {
			minDistance = -1;
		}
		
		System.out.println(minDistance);
	}
}

640ms 가 걸린다.