오늘 풀어본 문제는
백준 1956번 운동 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int [][] village;
    static final int INF = 4000000;
    public static void main(String[] args) throws IOException {
        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());

        village = new int[v+1][v+1];

        for(int [] i : village) Arrays.fill(i,INF);

        for(int i = 0; i < e; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            village[start][end] = weight;
        }


        for(int i = 1; i <= v; ++i)
        {
            for(int j = 1; j <= v; ++j)
            {
                for(int k = 1; k <= v; ++k)
                {
                    if(j == k || i == j || i == k) continue;
                    if(village[j][k] > village[j][i] + village[i][k]) village[j][k] = village[j][i] + village[i][k];

                }
            }
        }

        for(int i = 1; i <=v; ++i)
        {
            for(int j = 1; j <=v; ++j)
            {
                if(i == j) continue;
                if(village[i][i] > village[i][j] + village[j][i]) village[i][i] = village[i][j] + village[j][i];
            }
        }

        int max = Integer.MAX_VALUE;
        for(int i = 1; i <= v; ++i) if(village[i][i] != INF) max = Math.min(max,village[i][i]);

        int answer = -1;
        if(max != Integer.MAX_VALUE) answer = max;
        System.out.print(answer);
    }
}

📝 풀이

존재하는 사이클 중 최단경로를 찾는 문제입니다.

먼저 플로이드 와샬 알고리즘을 적용하여 각 마을간의 최단거리를 구해줍니다.

반복문이 1부터 순차적으로 수행되므로, 한번만 수행 할 경우 다른 경로들의 최솟값이 입력되기 이전에 각 사이클의 최솟값을 찾게됩니다.

따라서 저는 알고리즘을 한번 수행한 이후, 각 사이클이 존재하는지 먼저 확인하고, 존재한다면 그중 최소경로를 찾는 방식을 적용하여 풀었습니다.

📜 후기

이전에 몰랐던 알고리즘인 만큼 한번 이해했을 때 여러문제를 풀어보아야 겠다 생각이 들어서, 한 문제 더 풀어보았습니다!

확실히 다른 문제에 응용해보니 조금은 느낌이 달랐지만, 확실히 알고 넘어가니 다른문제에서도 적용할 수 있을 것 같습니다.