💡Problem Solving/BOJ

[BOJ 1956] 운동 (Java)

gom20 2021. 11. 13. 15:46

문제

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

 

1956번: 운동

첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의

www.acmicpc.net

 

풀이

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

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

 

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

문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22],..

gom20.tistory.com

 

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);

    }
}