(백준) #2458: 키 시퀀스(JAVA)

– 알고리즘 분류: Floyd-Warshall

– 언어: 자바

– 문제점

– Floyd-Warshall 알고리즘을 사용하여 모든 학생들과 비교가 이루어졌는지 확인합니다.

– 모든 학생들과 사이즈 비교를 했다면 사이즈 순서를 알 수 있습니다.

소스 설명은 주석을 참조하십시오.

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

public class Main {

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());       // 학생 수
        int M = Integer.parseInt(st.nextToken());       // 비교 수

        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        int()() map = new int(N+1)(N+1);

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map(a)(b) = 1;
            map(b)(a) = 2;

            // 1 : a보다 b가 큼. 2: b보다 a가 큼
        }

        for(int i=1; i<=N; i++){
            for(int from=1; from<=N; from++){
                for(int to=1; to<=N; to++){
                    if(map(from)(i) == 1 && map(i)(to) == 1){
                        map(from)(to) = 1;
                        map(to)(from) = 2;
                    }

                    else if(map(from)(i) == 2 && map(i)(to) == 2){
                        map(from)(to) = 2;
                        map(to)(from) = 1;
                    }
                }
            }
        }

        int num = 0;
        for(int i=1; i<=N; i++){
            boolean flag = false;
            for(int j=1; j<=N; j++){
                if(i == j) continue;

                // 모든 학생들이랑 비교를 한 적이 없으면 자기 순서를 모른다.


                if(map(i)(j) == 0){
                    flag = true;
                }
            }
            if(!
flag)
                num++;
        }

        System.out.println(num);
    }
}