[JAVA/플로이드 와샬] 백준 2458 키순서

1. 문제

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

2458번: 키 순서

 

2. 풀이

플로이드 와샬을 활용한 문제다.

문제의 예제에서 나온 그래프를 잘 보자. 여기서 순서를 정할 수 있는 노드는 <4>뿐이다. 4보다 큰사람이 <6>, <2>로 2명이고, 4보다 작은 사람이 <3>, <5>, <1>로 3명이므로 총 6명 중 나보다 큰 사람 2명, 나보다 작은 사람 3명 => 나는 3등 이라는 결론을 얻을 수 있는 것이다. 즉, 현재 노드가 다른 노드들과 모두 연결되어 있는 경우 순서를 따질 수 있으므로 나의 순서를 알 수 있다.

현재의 노드가 다른 노드들과 연결되어 있는 것을 확인하기 위해서는 플로이드 와샬 알고리즘을 쓴다. 플로이드 와샬을 사용해 각 점간의 거리를 구하고, 최종적으로 for문을 돌며 나와 나를 제외한 모든 노드들이 연결되어 있는 경우(=거리를 구할 수 있는 경우) 본인의 순위가 정해진다고 말할 수 있다.

 

3. 코드

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

// 플로이드 와샬

public class Main_2458 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int INF = 10000;
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int[][] d = new int[n+1][n+1]; // d[i][j]는 i서 j까지의 거리
        //모든 경로 INF로 채우기 
        for(int[] arr : d){ 
            Arrays.fill(arr, INF); 
        }
        
        while(m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            d[a][b] = 1; // 기존 경로 채우기
        }
        
        // 거쳐가는 노드
        for(int k = 1; k <= n; k++) {
            // 출발노드
            for(int i = 1; i <= n; i++) {
                // 도착노드
                for(int j = 1; j <= n; j++) {
                    if(d[i][j] == 0 || d[i][k] + d[k][j] < d[i][j]) {
                        d[i][j] = d[i][k] + d[k][j];
                    }
                }
            }
        }
        
        int answer = 0;
        for(int i = 1; i <= n; i++) {
            boolean isConnected = true;
            for(int j = 1; j <= n; j++) {
                if(i == j) continue; // 자기 자신 제외
                if(d[i][j] == INF && d[j][i] == INF) { // i와 j가 연결되어 있지 않으면
                    isConnected = false; // 정답이 아님
                    break;
                }
            }
            if(isConnected) answer++; // i가 모든 노드들과 연결됨
        }
        
        System.out.println(answer);
    }

}​