백준 1956번 운동 G4 - 플로이드 워셜 자바

 

 

이거 푸느라 운동 안간게 후회되네

 

아 집중 좀 하고 풀껄

후딱 풀거같아서 설렁설렁 확인하다 한참 걸린 문제다.  별것도 아닌게

 

집중 최고조 : 알려주려고 공부할때..

스터디 재밌당 ^<^

 

DP 문제 하려다 갑자기 땡겨서 누른 문제였다.. 왜그랬을까

 

간선에 가중치있는 그래프에서 최소경로를 찾을때는 플로이드 위샬을 사용했었다.

플로이드 워셜은 i 경로에서 j 경로까지 k를 통해 모든 경로를 업데이트하기 때문이다.

시간 복잡도는 이중 삼중 for문이기에 O(n³) 이다.

 

사이클을 찾는것을 확인하려면 i부터 j까지 갱신된 값이 존재한다면 사이클이 있다는 것이고,
초기에 세팅한 값이라면 -1 을 출력해주면 된다

 

간단하게 해결할 줄 알았는데... 

ㅋㅋ 헤헤

 

Math.max 오타 한번내고, 조건을 잘못 넣었어서 한참 걸렸었다..

if (arr[i][j] != max && arr[j][i] != max)

 

플로이드 워셜로 값 갱신할때 이 조건을 넣었었는데 사이클 찾을때만 필요했지
오히려 업데이트를 안해버려서 문제가 생겼었다.

 

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {// Boj_1956_운동
    // 플로이드 워샬 예제
    public static int V, N, a, b, c, answer, max;
    public static int[][] arr;
 
    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());
        N = Integer.parseInt(st.nextToken());
        arr = new int[V + 1][V + 1];
        max = 1000000000;
 
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                arr[i][j] = max;
            }
        }
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken()); // start
            b = Integer.parseInt(st.nextToken()); // end
            c = Integer.parseInt(st.nextToken()); // cost
            arr[a][b] = c;
        }
        // 플로이드 워샬
        for (int k = 1; k <= V; k++) {
            for (int i = 1; i <= V; i++) {
                for (int j = 1; j <= V; j++) {
                        arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]);
                }
            }
        }
        answer = max;
        // 사이클을 찾아준다.
        for (int i = 1; i <= V; i++) { // 시작점
            for (int j = 1; j <= V; j++) { // 끝점
                if (arr[i][j] != max && arr[j][i] != max) {
                    answer = Math.min(answer, arr[i][j] + arr[j][i]);
                }
            }
        }
        answer = max == answer ? -1 : answer;
        System.out.println(answer);
    }
}
 

 

에잉..