[JAVA] 백준 끝나지 않는 파티(플로이드워셜)

플로이드 워셜 문제로 풀어야 시간초과가 나지 않는 문제이다.

단뱡향 노드로 모든 길에 대한 값이 들어가있는 문제에서 사용!

플로이드워셜

시행착오

1. BFS로 각각의 케이스에 대해서 따로 최단거리를 구하려했다

=> 파티장의 크기 N(5 ≤ N ≤ 500) , 파티장의 번호, C(1 ≤ C ≤ 1,000,000,000) 이므로 BruteForce(N * N = 2500)로 한번에 모든 거리를 구해놓아야 한다는 것을 깨달았다.

2. 완전탐색(Brute-Force)으로 모든것을 탐색할때 BFS방식으로 탐색했다.

=> 이미 진행한 길에 대해서 추가적인 낭비 노드가 발생한다.

 

따라서 플로이드 워셜로 순차적으로 업데이트 해나가는 삼중for문 방식이 더 효율적인 것을 알 수 있었다.

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

public class Main {
    static int N, M;
    static int p[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        p = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                p[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        /*for (int i = 0; i < N; i++) {//bruteforce
            for (int j = 0; j < N; j++) {
                p[i][j] = bfs(i,j,p[i][j]);
            }
        }
*/
        //플로이드워셜
        for (int k = 0; k <N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j <N; j++) {
                    p[i][j]= Math.min(p[i][j], p[i][k] + p[k][j]);
                }
            }
        }


        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken());
            boolean canGo = c >= p[a][b];

            if (canGo) sb.append("Enjoy other party").append('\n');
            else sb.append("Stay here").append('\n');
        }
        System.out.print(sb.toString());
    }
/*
    static class Node {
        int x, time;
        public Node(int x, int time) {
            this.x = x;
            this.time = time;

        }
    }

    private static int bfs(int a, int b, int c) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(a, 0));
        int shortestTime = c;

        while (!q.isEmpty()) {
            Node n = q.poll();
            if (n.time > c) continue;
            if (n.x == b) {
                shortestTime = Math.min(shortestTime, n.time);
                continue;
            }
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i != n.x) q.add(new Node(i, n.time + p[n.x][i]));
                }
            }
        }

        return shortestTime;
    }*/
}

주석 처리된부분은 시간초과로 정답처리 되지않는 방식이다.

 

위 코드에서 봐야할 부분은 플로이드 워셜 알고리즘 부분이다.

//플로이드워셜
        for (int k = 0; k <N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j <N; j++) {
                    p[i][j]= Math.min(p[i][j], p[i][k] + p[k][j]);
                }
            }
        }

k가 맨위 for문이다! 즉, 사이에 끼는것이 맨위에 있다고 기억!!

(i -> j) vs ( ( i-> k) + ( k -> j) )