[백준, 1956, G4] 운동

0. 문제 링크

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

1956번: 운동

---

1. 문제 핵심

1. 일방 통행 도로로 이루어진 V개 마을과 E개 도로로 구성된 도시가 있다.
2. 사이클이 형성된 최소 도로를 찾아야 한다.

---

2. 문제 접근

1. 처음에는 MST로 간선치가 작은 선분부터 집어넣고 사이클이 형성되었으면 BFS로 최소 경로 비용을 찾기로 했습니다. 하지만 역시 시간 초과, 메모리 초과로 해결할 수 없었습니다.
2. 질문 확인 결과 사이클 == 플루이드 워샬 이라는 것을 알 수 있었고 기존에 알던 지식으로 해결하려 했습니다.
3. 사이클 형성이 관건이기 때문에 자기 자신인 대각선 중에서 가장 작은 수를 반환하면 되리라 생각했는데 사이클 계산이 잘 되지 않아서 이 부분은 참고를 했습니다.
4. 새롭게 배운 것인데 최소 사이클이 관건이기 때문에 모든 배열을 맥스 값으로 초기화하고 플루이드 워샬을 돌릴 때 맥스 값이 아닌 것들을 서로 이으면서 기존에 이어진 것보다 작은 것들만 이어지게끔 구현하면 되는 것이었습니다.

---

3. 코드 분석

k, i, j 순서를 항상 숙지할 것.

더 작은 값으로 연결 가능할 때만 연결해주면 문제 없이 사이클을 구할 수 있습니다.

---

4. 베스트 코드 분석

---

5. 코드

package _1023.LC;

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

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

		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		int[][] bd = new int[V + 1][V + 1];
		for (int i = 1; i <= V; i++) {
			Arrays.fill(bd[i], Integer.MAX_VALUE);
		}
		boolean[] visit = new boolean[V + 1];
		int s, e, w;
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			bd[s][e] = w;
		}
		for (int k = 1; k <= V; k++) {
			for (int i = 1; i <= V; i++) {
				for (int j = 1; j <= V; j++) {
					if (bd[i][k] == Integer.MAX_VALUE || bd[k][j] == Integer.MAX_VALUE)
						continue;
					if (bd[i][k] + bd[k][j] < bd[i][j])
						bd[i][j] = bd[i][k] + bd[k][j];
				}
			}
		}
		int answer = Integer.MAX_VALUE;
		for (int i = 1; i <= V; i++) {
			if (bd[i][i] != -1)
				answer = Math.min(answer, bd[i][i]);
		}
		if (answer == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
	}
}