[백준] 1956. 운동

문제 링크

[백준] 1956. 운동

풀이 과정

플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로 가는 최소 비용을 구하는 알고리즘입니다. 본 문제는 각 노드를 시작으로 생성되는 모든 사이클 중, 비용이 최소인 사이클을 구하는 문제입니다.

for (int k = 1; k <= V; k++) {
    for (int i = 1; i <= V; i++) {
        if (i == k) continue;
        for (int j = 1; j <= V; j++) {
            if (j == k || j == i) continue;
            if (dist[i][j] > dist[i][k] + dist[k][j])
                dist[i][j] = dist[i][k] + dist[k][j];
        }
    }
}

위 코드는 플로이드-워셜 알고리즘을 적용하는 부분으로, 모든 정점에 대해 경유하는 정점(k)을 설정하고, 시작 정점(i)에서 목적지 정점(j)으로 가는 최소 비용을 갱신합니다.

int answer = MAX;
for (int i = 1; i <= V; i++) {
    for (int j = 1; j <= V; j++) {
        if (i == j) continue;
        if (dist[i][j] != MAX && dist[j][i] != MAX) {
            answer = Math.min(answer, dist[i][j] + dist[j][i]);
        }
    }
}

사이클의 형성 유무는 플로이드-워셜 알고리즘을 적용시킨 후, dist[i][j] 와 dist[j][i] 값이 초기 설정해 둔 MAX 값인지를 체크하면 판단할 수 있습니다. dist[i][j] 요소가 MAX 값에서 갱신되었다면, 이는 정점 i에서 최소 하나 이상의 다른 정점을 거쳐 j로 이동했음을 의미합니다. 따라서 dist[i][j]와 dist[j][i] 값이 모두 MAX가 아닌 어떠한 갱신된 값이라면, 이는 정점 i를 시작으로 사이클이 생성됨을 의미하게 됩니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt();
        int E = sc.nextInt();

        final int MAX = 987654321;
        int[][] dist = new int[V + 1][V + 1];
        for (int i = 1; i <= V; i++) Arrays.fill(dist[i], MAX);

        for (int i = 0; i < E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            dist[a][b] = c;
        }

        for (int k = 1; k <= V; k++) {
            for (int i = 1; i <= V; i++) {
                if (i == k) continue;
                for (int j = 1; j <= V; j++) {
                    if (j == k || j == i) continue;
                    if (dist[i][j] > dist[i][k] + dist[k][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }

        int answer = MAX;
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i == j) continue;
                if (dist[i][j] != MAX && dist[j][i] != MAX) {
                    answer = Math.min(answer, dist[i][j] + dist[j][i]);
                }
            }
        }

        System.out.println(answer == MAX ? -1 : answer);
    }
}