[Baekjoon] 1956_운동

Gold IV

문제(출처: https://www.acmicpc.net/problem/1956)

---

< 운동 >

 

문제 풀이 

 

먼저 a번 마을에서 b번 마을까지의 최단 거리를 찾은 후 b번 마을에서 다시 a번으로 올 수 있는지를 확인하여 최단 거리를 구한다.

 

 

 my solution (Java)

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

public class _1956_ { // 운동

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());

		int arr[][] = new int[v][v];
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				if (i == j)
					arr[i][j] = 0;
				else
					arr[i][j] = Integer.MAX_VALUE;
			}
		}

		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			arr[a - 1][b - 1] = c;
		}

		// [시작, 끝] = [시작, 중간]+[중간, 끝]
		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				for (int k = 0; k < v; k++) {
					if (arr[j][i] == Integer.MAX_VALUE || arr[i][k] == Integer.MAX_VALUE)
						continue;
					arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
				}
			}
		}

		int result = Integer.MAX_VALUE;

		for (int i = 0; i < v; i++) {
			for (int j = 0; j < v; j++) {
				if (i == j || arr[i][j] == Integer.MAX_VALUE || arr[j][i] == Integer.MAX_VALUE)
					continue;

				if (arr[i][i] != 0)
					arr[i][i] = Math.min(arr[i][i], arr[i][j] + arr[j][i]);
				else
					arr[i][i] = arr[i][j] + arr[j][i];

				result = Math.min(result, arr[i][i]);
			}
		}

		if(result==Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(result);
	}
}

 

Main

변수)
v, e : 마을 개수, 도로 개수
arr : 최단 거리
a, b, c : a번 마을에서 b번 마을로 가는 거리 c
result : 최소 사이클의 도로 길이의 

 

- 마을 개수(v), 도로 개수(e) 입력

- a번 마을에서 b번 마을로 가는 거리 c 저장

- [시작 마을, 끝 마을] = [시작 마을, 중간 마을]+[중간 마을, 끝 마을]을 구함

- 사이클을 찾아야 하므로 [시작 마을, 시작 마을] = [시작 마을, 끝 마을] + [끝 마을, 시작 마을]인 것을 찾으면서 최소 사이클의 도로 길이 합을 구함 

- 최소 사이클의 도로 길이 합(result) 출력

---

---