[자바] 백준 1956 - 운동 (java)

목차

문제 : boj1956

 

 

필요 알고리즘

• 플로이드-워셜 (floyd-warshall)
  
  • 다른 그래프 탐색 알고리즘으로 되긴 하겠지만, 이 문제는 플로이드 워셜이 매우 편하긴 하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  단방향 그래프에서 '1번 마을에서 1번 마을로 가는 최소 거리, 2번 마을에서 2번 마을로 가는 최소 거리, ... , V번 마을에서 V번 마을로 가는 최소 거리' 중 최소값을 출력하면 되는 문제이다.

int answer = INF;
for (int i = 1; i <= v; i++) {
    answer = Math.min(answer, arr[i][i]);	// 1~V 마을에 대해 i번 마을에서 i번 마을로 가는 최소 거리가 답!
}

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

 

  내 경우 이런류의 많은 지점에서 많은 지점으로의 탐색 문제를 보면 일단 노드의 개수부터 본다. 400개? 그럼 구현도 간단하고 매우 강력하지만 O(N^3)인게 유일한 문제점인 플로이드 워셜을 쓰면 된다는 얘기다 ㅋㅋ

 

  그래서 무지성 플로이드-워셜로 풀었다.

for (int k = 1; k <= v; k++) {
    for (int i = 1; i <= v; i++) {
        for (int j = 1; j <= v; j++) {

            arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]);

        }
    }
}

 

 

코드 : github

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    static final int INF = 4000001;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        int[][] arr = new int[v+1][v+1];
        for (int[] row : arr) Arrays.fill(row, INF);
        while (e-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            arr[a][b] = c;
        }

        for (int k = 1; k <= v; k++) {
            for (int i = 1; i <= v; i++) {
                for (int j = 1; j <= v; j++) {

                    arr[i][j] = Math.min(arr[i][k] + arr[k][j], arr[i][j]);

                }
            }
        }

        int answer = INF;
        for (int i = 1; i <= v; i++) {
            answer = Math.min(answer, arr[i][i]);
        }

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