백준 1956 운동 - JAVA

1956 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int V;
    static int[][] dist;
    static List<int[]>[] graph;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        dist = new int[V + 1][V + 1];
        for (int i = 1; i <= V; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        graph = new ArrayList[V + 1];
        for (int i = 0; i <= V; i++) {
            graph[i] = new ArrayList<>();
        }
        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());
            dist[a][b] = c;
        }
        floid();
        bw.write(String.valueOf(findMinCycle()));
        bw.flush();
    }
    private static void floid() {
        for (int k = 1; k <= V; k++) {
            for (int i = 1; i <= V; i++) {
                for (int j = 1; j <= V; j++) {
                    if (dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    private static int findMinCycle() {
        int answer = Integer.MAX_VALUE;
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i == j) continue;
                if (dist[i][j] != Integer.MAX_VALUE && dist[j][i] != Integer.MAX_VALUE) {
                    answer = Math.min(answer, dist[i][j] + dist[j][i]);
                }
            }
        }
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}

 

알고리즘 설명

---

플로이드 - 워셜 알고리즘은 그래프 내 모든 정점 쌍에 대한 최단 거리를 계산하는 방식이므로, 단일 출발점이 아닌 전체 경로 정보가 필요한 문제에 적합한 알고리즘입니다. (단일 출발점에서 최단 경로는 다익스트라 알고리즘이 적합)

 

해당 문제에서도 가장 짧은 사이클을 찾으라고 했기 때문에 플로이드 - 워셜 알고리즘을 사용하는 것이 적합할 것 같습니다.

 

핵심 아이디어는 정점 i에서 j로 가는 최단거리를 구해야하므로, 어떤 두 정점 i, j가 있을 때 i -> j로 가는 경로와 j -> i로 가는 경로가 존재한다면, i -> j -> i로 사이클을 이루므로 dist[i][j] + dist[j][i]값을 계산하여 그 중 최솟값을 구하면 될 것 같습니다.

 

 

코드 해석

---

먼저, 정점의 개수 V와 간선의 개수 E를 입력받고, 모든 정점 쌍 간의 최단 거리를 저장하기 위한 dist[][] 배열을 초기화합니다. 이때 초기값은 도달할 수 없는 상태를 의미하도록 Integer.MAX_VALUE로 설정합니다.

 

이후 입력으로 주어진 방향 간선 정보를 바탕으로 dist[a][b]에 가중치 c를 저장하여 초기 그래프 상태를 구성합니다.

 

플로이드–워셜 알고리즘을 수행하여 모든 정점 쌍 (i, j)에 대해 최단 거리를 계산합니다. 중간 정점 k를 하나씩 경유지로 선택하며,

i → k → j 경로가 기존의 i → j 경로보다 짧은 경우 최단 거리를 갱신합니다. 이 과정에서 아직 경로가 존재하지 않는 경우를 처리하기 위해, 두 경로 중 하나라도 무한대인 경우는 계산에서 제외합니다.

 

모든 정점 쌍의 최단 거리 계산이 완료되면, 그래프 내에 존재하는 최소 사이클을 탐색합니다. 두 경로의 거리 합 dist[i][j] + dist[j][i]를 계산하여, 가능한 모든 사이클 중 최소 비용을 갱신합니다.

 

모든 정점 쌍을 검사한 이후에도 변수 answer의 값이 Integer.MAX_VALUE(사이클이 발견되지 않음)라면 -1을 반환하고, 하나라도 존재할 경우 최소 비용 사이클의 길이를 결과로 출력합니다.