백준 2458 - 키 순서

문제

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

리뷰

플로이드 워셜을 이용하여 풀이할 수 있느 문제였다.

문제에서 주어진 그래프는 방향 그래프이다. 이 그래프에서 주어진 조건대로
간선에 1의 가중치를 부여하여 방향 그래프를 설정하였을때 키 순서를 알 수 있는
정점 $k$는 다음과 같이 정의할 수 있다.

$map[1..N][k]$중 경로가 존재하는 경우 +
$map[k][[1..N]$중 경로가 존재하는 경우=$N-1$개

위 정의에 따라 플로이드 워셜 로직을 수행한 후 정점별로 경우를 카운팅해주어
그 개수가 $N-1$인 것만 셈해주면 정답을 도출할 수 있다.

로직의 시간복잡도는 플로이드 워셜을 수행하는 부분에서 $O(N^3)$으로 수렴하므로
$N=500$인 최악의 경우에도 무난히 제한 조건 1초를 통과할 수 있다.

코드

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

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

public class Main {
    static int N;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N=parseInt(st.nextToken());
        int M=parseInt(st.nextToken());

        map=new int[N+1][N+1];

        initMap();
        int i, j;
        while(M-->0){
            st=new StringTokenizer(br.readLine());
            i=parseInt(st.nextToken());
            j=parseInt(st.nextToken());

            map[i][j]=1;
        }

        floyd();

        int result=0;

        for(i=1; i<=N; i++){
            int count=0;

            for(j=1; j<=N; j++){
                if(i==j) continue;

                if(map[i][j]!=MAX_VALUE || map[j][i]!=MAX_VALUE)
                    count++;
            }

            if(count==N-1) result++;
        }

        System.out.println(result);
        br.close();
    }

    static void initMap(){
        for(int i=1; i<map.length; i++)
            for(int j=1; j<map[i].length; j++){
                if(i==j) continue;

                map[i][j]=MAX_VALUE;
            }
    }


    static void floyd(){
        for(int k=1; k<=N; k++)
            for(int i=1; i<=N; i++)
                for(int j=1; j<=N; j++){
                    if(map[i][k]==MAX_VALUE || map[k][j]==MAX_VALUE)
                        continue;

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

결과