[BOJ 1956] 운동 (Java)

문제

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

1956번: 운동

 

풀이

아래 문제랑 비슷한데, 해당 문제는 플로이드 와샬 알고리즘을 이용해 푸는게 가능하다.

2021.10.31 - [Problem Solving/Programmers] - [프로그래머스] 합승 택시 요금 (Java)

[프로그래머스] 합승 택시 요금 (Java)

 

Vertex 개수의 2차 배열을 만들어서 행과 열을 출발지와 목적지로 간주한다. 

자기 자신은 0으로 채우고 나머지 값은 거리의 최대값을 초과하는 값으로 넣어준다. 

입력 받은 거리 정보를 채워넣는다. 

i -> j 와 i -> k -> j 거리를 비교하여 작은 값으로 갱신한다. 

        for(int k = 1; k <= V; k++){
            for(int i = 1; i <= V; i++){
                for(int j = 1; j <= V; j++){
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

이후 floyd[i][j] + floyd[j][i] 의 최소 값을 구한다. (사이클)

소스코드

package floyd;

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

public class BOJ1956 {

    public static void main(String[] args) throws Exception {
        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[][] floyd = new int[V+1][V+1];

        for(int i = 1; i <= V; i++){
            for(int j = 1; j <= V; j++){
                if(i == j) floyd[i][j] = 0;
                else floyd[i][j] = 10001;
            }
        }

        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());
            floyd[a][b] = c;
        }

        for(int k = 1; k <= V; k++){
            for(int i = 1; i <= V; i++){
                for(int j = 1; j <= V; j++){
                    floyd[i][j] = Math.min(floyd[i][j], floyd[i][k] + floyd[k][j]);
                }
            }
        }

        long min = Long.MAX_VALUE;
        boolean exist = false;
        for(int i = 1; i <= V; i++){
            for(int j = 1; j <= V; j++){
                if(i == j) continue;
                if(floyd[i][j] == 10001 || floyd[j][i] == 10001) continue;
                exist = true;
                min = Math.min(min, floyd[i][j] + floyd[j][i]);
            }
        }

        System.out.println(exist? min : -1);

    }
}