b1956. 운동

 

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

 

 

 

📌 자바(Java)로 푸는 운동 문제 - 백준 1956 🚴‍♂️

🔎 문제 개요

 

백준 1956번 - 운동 문제입니다.

V개의 마을과 E개의 도로가 주어졌을 때,

“한 마을에서 출발하여 다시 그 마을로 돌아오는 최소 사이클의 길이” 를 구하는 문제입니다.

🚴 즉, 최단 사이클(순환 경로)의 길이를 찾는 것이 핵심입니다.

 

---

💡 예제 입력

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

💡 예제 출력

3

➡ 최단 사이클의 길이가 3인 경우를 찾아 출력

 

---

🛠 알고리즘 접근 방식

 

이 문제를 해결하기 위해 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 을 사용합니다.

 

✏️ 주요 고려 사항

 

✔ 모든 정점 간 최단 경로를 계산해야 함

✔ 각 정점에서 시작하여 다시 자기 자신으로 돌아오는 최소 비용을 찾아야 함

✔ 플로이드-워셜 알고리즘을 활용하여 O(V³) 복잡도로 해결 가능

 

---

🔹 Java 코드 해설

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

public class Main {

    static int V, E;
    static int INF = 40000000;  // 충분히 큰 값 설정
    static int[][] graph;

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

        V = stringToInt(st.nextToken());
        E = stringToInt(st.nextToken());

        graph = new int[V + 1][V + 1];
        for (int i = 0; i <= V; i++)
            Arrays.fill(graph[i], INF);

        for (int i = 0; i <= V; i++)
            graph[i][i] = 0;  // 자기 자신으로 가는 경로는 0

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = stringToInt(st.nextToken());
            int b = stringToInt(st.nextToken());
            int c = stringToInt(st.nextToken());

            graph[a][b] = c;
        }  // 입력 종료

        logic();

        int answer = INF;
        for (int i = 1; i <= V; i++) {
            answer = Math.min(answer, graph[i][i]);  // 자기 자신으로 돌아오는 최단 경로 찾기
        }
        System.out.println((answer == INF) ? -1 : answer);
    }

    static void logic() { // 플로이드-워셜 알고리즘
        for (int k = 1; k <= V; k++) { // 경유지
            for (int i = 1; i <= V; i++) { // 출발지
                for (int j = 1; j <= V; j++) { // 도착지
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    static int stringToInt(String s) {
        return Integer.parseInt(s);
    }
}

 

---

🔍 코드 설명

 

📌 1. 그래프 입력 및 초기화

graph = new int[V + 1][V + 1];
for (int i = 0; i <= V; i++)
    Arrays.fill(graph[i], INF);

for (int i = 0; i <= V; i++)
    graph[i][i] = 0;  // 자기 자신으로 가는 경로는 0

✔ INF(40000000) 값으로 초기화하여 최소값 비교에 활용

✔ 자기 자신으로 가는 경로는 0으로 설정

 

---

📌 2. 플로이드-워셜 알고리즘 수행

for (int k = 1; k <= V; k++) { // 경유지
    for (int i = 1; i <= V; i++) { // 출발지
        for (int j = 1; j <= V; j++) { // 도착지
            if (graph[i][j] > graph[i][k] + graph[k][j]) {
                graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }
}

✔ 모든 정점 간 최단 경로를 갱신

✔ 플로이드-워셜 알고리즘을 통해 O(V³) 시간 안에 해결 가능

 

---

📌 3. 최소 사이클 길이 찾기

int answer = INF;
for (int i = 1; i <= V; i++) {
    answer = Math.min(answer, graph[i][i]);  // 자기 자신으로 돌아오는 최단 경로 찾기
}
System.out.println((answer == INF) ? -1 : answer);

✔ 자기 자신으로 돌아오는 최단 경로 중 최소값을 찾아 출력

✔ 사이클이 없는 경우 -1 출력

 

---

🏆 정리

✅ 핵심 포인트

 

✔ 플로이드-워셜 알고리즘을 사용하여 모든 정점 간 최단 경로를 계산

✔ 자기 자신으로 돌아오는 최단 경로 중 최소값을 찾아 출력

✔ O(V³) 시간 복잡도로 해결 가능

 

---

🎯 이 알고리즘의 장점

 

✅ 모든 정점 간 최단 경로를 계산 가능

✅ 음수 가중치가 있어도 적용 가능 (음수 사이클은 허용하지 않음)

✅ 코드가 직관적이고 구현이 간단함

 

---

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊