백준 2458번 키 순서 (Java)

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

 

한 노드에서 다른 노드의 대한 정보를 알 수 있는가를 묻는 문제이다. 방법은 두개가 있다. 

1. 각 지점에서 모두 dfs해보며 갈 수 있는지 검사한다. 

2. 플로이드 워셜을 사용한다. 

 

이 문제의 의도는 2번이기 때문에 2번의 의미를 알아보도록 하자 플로이드 워셜은 다익스트라와 달리 각 모든 노드들의 최단거리를 알아볼 수 있는 알고리즘이다.

 

예를들어 A 노드에서 B노드로 가는 방법에는 두가지가 있을 것이다. 

 

1. A -> B로 바로 가는 경우

2. A -> C - > B 어떤 노드를 경유할 경우

 

그리고 이 둘 중 작은 값이 최단거리가 된다. 

dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j])

 

위를 이해했다면 이제 모든 거리에 따라 위 점화식을 대입해주면된다. 그리고 중요한 건 플로이드 워셜은 우선 행렬로 나타내는 것이 먼저이다. 이제 이것을 알고 저문제에 대입해보면 만약 플로이드 워셜을 실행했을 때 dist 행렬에 INF 라면 이 둘은 만나지 못했다는 의미이기 때문에 키 순서를 알 수 없다고 판단된다.

 

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

import static java.lang.Integer.max;
import static java.lang.Integer.parseInt;

public class Main {
    static int[][] heights = new int[501][501];
    static int[][] revheight = new int[501][501];

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

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        for (int i = 0; i <= n; i++){
            for(int j = 0; j <= n; j++){
                heights[i][j] = 1000000;
                revheight[i][j] = 1000000;
            }
        }

        for(int i = 0; i < m; i++) {
            String[] tmp = br.readLine().split(" ");
            int a = Integer.parseInt(tmp[0]);
            int b = Integer.parseInt(tmp[1]);

            heights[a][b] = 1;
            revheight[b][a] = 1;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    heights[j][k] = Integer.min(heights[j][k], heights[j][i] + heights[i][k]);
                    revheight[j][k] = Integer.min(revheight[j][k], revheight[j][i] + revheight[i][k]);
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++){
            int cnt = 0;
            for(int j = 1; j <= n; j++){
                if(i == j) continue;
                if(heights[i][j] < 1000000 || revheight[i][j] < 1000000){ // 1 - 2- 3 // 4 - 5
                    cnt++;
                }
            }
            if(cnt == n - 1){
                answer++;
            }
        }

        System.out.println(answer);
    }
}