[BOJ1956] 운동 (플로이드 워셜)

 

 

---

문제 링크 

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

1956번: 운동

 

문제 풀이 

- 플로이드 워셜 카테고리 문제 (카테고리 몰랐으면 과연 풀었을까 싶다)

- 노드별 사이클 발생할 경우 최단 거리 구함(시작 노드를 포함하는) 

- 시간 복잡도 : O(N^3) 

 

플로이드 워셜의 경우 각 노드별로 다른 노드로 가는 최단 거리를 구하게 된다

이때 사이클이 발생한다는 것은 각 시작 노드의 최단 거리 값이 INF가 아니게 된다는 의미로 해석해서 풀이했다

 

ex) (1,1), (2,2), (3,3)이 INF가 아닌 경우 사이클 발생으로 판단

입력 

3 4
1 2 1
3 2 1
1 3 5
2 3 2

 

초기화

	1	2	3
1	INF	1	5
2	INF	INF	2
3	INF	1	INF

 

플로이드 워셜 결과

	1	2	3
1	INF	1	3
2	INF	3	2
3	INF	1	3

 

참고. 다른 풀이 방법에 대해 찾아 보았는데 아래와 같은 형태로 구하는 것으로 확인되었다. (좀 더 명시적인 듯하다)

1) i == j 제외한 플로이드 워셜 수행 

2) 2중 반복문을 돌며 dist[i][j] != INF && dist[j][i] != INF 사이클이라 판단하고 정답 갱신

https://steady-coding.tistory.com/101

[BOJ] 백준 1956번 : 운동 (JAVA)

 

제출 코드

Integer.MAX_VALUE로 최대치 지정시 음수 값을 출력하기 때문에 적당히 최대치를 지정함

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

public class Main {
    
    static int V, E;

    static int[][] dist;

    static int INF = 4000001;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); // 노드
        E = Integer.parseInt(st.nextToken()); // 간선

        dist = new int[V + 1][V + 1];
        for(int i = 1; i <= V; i++) {
            Arrays.fill(dist[i], INF);
        }

        for(int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            dist[from][to] = cost;
        }
    }

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

       int ans = INF;
       for(int i = 1; i <= V; i++) {
           ans = Math.min(ans, dist[i][i]);
       }

        System.out.println(ans == INF ? -1 : ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}