백준 1956 (운동) - java

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

1956번: 운동

유형 : 플로이드 - 와샬

접근

• 사이클에 대한 문제이기 때문에 다익스트라는 사용하지 못한다.
• 사이클 판단은 크게 2가지로 분류된다.
  • 방향 그래프 -> DFS
  • 무방향 그래프 -> Union - Find
• 위 문제는 방향 그래프라서 DFS를 사용할까 생각했다. 하지만 그럴 경우에는 해당 문제를 해결할 수 없다. (풀더라도 시간초과)

Why ?

모든 지점에서 사이클을 판단하기 위한 BFS를 매번 새로 수행해줘야 하기 때문이다.

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int n = 0;
    static int m = 0;

    static int[][] board;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][n+1];

        for(int i=1;i<=m;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            board[x][y] = v;
        }

        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(board[i][k] > 0 && board[k][j] > 0){
                        if(board[i][j] == 0){
                            board[i][j] = board[i][k] + board[k][j];
                        }

                        else{
                            board[i][j] = Math.min(board[i][j] , board[i][k] + board[k][j]);
                        }
                    }

                }
            }
        }

        int result = -1;

        for(int i=1;i<=n;i++){
            if(board[i][i] == 0)
                continue;

            if(result == -1)
                result = board[i][i];

            else{
                result = Math.min(result , board[i][i]);
            }
        }

        System.out.println(result);
        br.close();