<BOJ> 1956 자바 (운동)

Bacha Coffee, Singapore

 

 

이번 문제는 플로이드-워셜 알고리즘에 대해 먼저 이해하고 풀어야한다!

플로이드-워셜(floyd-warshall)

 

DFS 풀이 코드(1% 시간초과)

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

public class 운동 {
    private  static ArrayList<int[]>[] a;
    private static boolean visited[][];
    private static int min = Integer.MAX_VALUE;
    static int start;
    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());

        a = new ArrayList[V+1];
        for (int i = 1; i <= V; i++) {
            a[i] = new ArrayList<>();
        }
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            a[Integer.parseInt(st.nextToken())].add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }
        for (int s = 1; s <= V; s++) {
            visited = new boolean[V+1][V+1];
            start = s;
            dfs(s,0);
        }
        if(min == Integer.MAX_VALUE) {
            System.out.println(-1);
        }else {
            System.out.println(min);
        }


    }

    private static void dfs(int v, int sum) {

        for(int[] i : a[v]){
            if (visited[v][i[0]]) {
                continue;
            }
            visited[v][i[0]] = true;
            if(i[0]==start) {
                // min 체크
                min = min > sum + i[1] ? sum + i[1] : min;
                continue;
            }
            dfs(i[0], sum + i[1]);
        }
    }
}

 

DFS로 푸니 바로 시간초과가 발생했다.

플로이드 워셜에 대해 공부해보니 이번 문제는 플로이드 워셜로 풀어야 시간초과없이 효과적으로 풀 수 있는 문제였다.

 

1. 플로이드-워셜로 모든 노드의 최단거리 배열을 구하고

2. 1에서 구한 배열을 전체 순회하면서 S==E가 될 때마다 MIN을 비교하고 갱신

3. MIN을 출력

 

풀이 코드 (플로이드-워셜1)

package algorithms.src.단기간성장;

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

public class 운동_플로이드워셜 {
    private static int[][] floydMap;
    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());

        floydMap = new int[V][V];
        int INF = 100000000;
        // 초기화 1
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if(i==j) floydMap[i][j] = INF;
                else floydMap[i][j] = INF;  // 무한대로 세팅
            }
        }
        // 초기화 2
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            floydMap[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = Integer.parseInt(st.nextToken());
        }

        // 플로이드 워셜
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    floydMap[i][j] = Math.min(floydMap[i][j], floydMap[i][k] + floydMap[k][j]);
                }
            }
        }
        int min = INF;
        for (int i = 0; i < V; i++) {
            min = min < floydMap[i][i] ? min : floydMap[i][i];
        }
        if(min == INF) System.out.println(-1);
        else System.out.println(min);
    }
}

* 플로이드 워셜을 변형했다. 자기자신을 가리킬 때 초기값이 0이아닌 INF로 지정했다.

   -> 그 이유는 자기 자신으로 돌아오는(사이클) 최소값을 구해야하니 플로이드-워셜 점화식에 자기자신도 포함되어야 할 것 같아서 인데,

        일단 맞긴했다..

   -> 플로이드 워셜을 정석대로 사용하려면 아래 코드가 될 것이다.

 

풀이 코드 (플로이드-워셜 2)

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

public class 운동_플로이드워셜 {
    private static int[][] floydMap;
    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());

        floydMap = new int[V][V];
        int INF = 100000000;
        // 초기화 1
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if(i==j) floydMap[i][j] = 0;
                else floydMap[i][j] = INF;  // 무한대로 세팅
            }
        }
        // 초기화 2
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            floydMap[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = Integer.parseInt(st.nextToken());
        }

        // 플로이드 워셜
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    floydMap[i][j] = Math.min(floydMap[i][j], floydMap[i][k] + floydMap[k][j]);
                }
            }
        }
        int min = INF;
        for (int i = 0; i < V; i++) {
            int tmp = 0;
            for (int j = 0; j < V; j++) {
                if (i != j && floydMap[i][j] != INF && floydMap[j][i] != INF) {
                    tmp = floydMap[i][j] + floydMap[j][i];
                    min = Math.min(min, tmp);
                }
            }
        }
        if(min == INF) System.out.println(-1);
        else System.out.println(min);
    }
}

* 10번정도 63%에서 틀렸는데 INF값을 올리니 해결되었다.

 

위: 풀이2 / 아래: 풀이1