[BOJ/JAVA] 2458번: 키 순서

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

2458번: 키 순서

키워드

N명의 학생들의 키는 모두 다르다.

학생의 수의 최댓값은 500이다.

a번 학생의 키가 b번 학생의 키보다 작다면 a→b 그래프가 연결된다.

자신의 키가 몇 번째인지 알 수 있는 학생이 몇명인지 계산하자.

---

1. N명의 학생들의 키는 모두 다르다.

이를 통해서 연결된 정보만을 통해 학생 구분이 가능하다.

---

2. 학생의 수의 최댓값은 500이다.

a번 학생의 키가 b번 학생의 키보다 작다면 a→b 그래프가 연결된다.

그래프를 인접매트릭스 형태로 구현할 수 있다.

---

3. 자신의 키가 몇 번째인지 알 수 있는 학생이 몇명인지 계산하자.

자신의 키가 몇 번째인지 알 수 있는 방법은

1. 나보다 키가 큰 학생의 수
2. 나보다 키가 작은 학생의 수

1+2 가 N-1(자기 자신 제외)이 되어야 한다.

i 학생보다 키가 큰 학생은 그래프로 연결이 되므로

i학생보다 키가 큰 학생은 연결된 경로를 모두 찾아가면 된다.

예를 들어서 a학생이 b학생보다 작고, b학생이 c학생보다 작으면

a→b→c 형태의 그래프가 나온다.

이를 FloydWarshall 알고리즘을 이용하여 a에서 c로 갈 수 있는지 판단하면 된다.

반대로 i학생보다 작은 학생의 수를 계산하기 위해서

i학생으로 들어오는 학생의 수를 계산하면 된다.

---

코드

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

public class java_2458 {
    // 전체 학생의 수
    static int N;
    // 학생의 키를 비교한 횟수
    static int M;
    // 학생 테이블
    static boolean board[][];

    static void floydWarshall() {
        // [i] 를 경유하여
        for (int i = 0; i < N; i++) {
            // [j] 로부터 출발하여
            for (int j = 0; j < N; j++) {
                // [k] 로 가는 경우
                for (int k = 0; k < N; k++) {
                    if (board[j][k] == false) {
                        if (board[j][i] != false && board[i][k] != false) {
                            board[j][k] = true;
                        }
                    }
                }
            }
        }
    }

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

        // N명의 학생의 키는 전부 다르다
        // 1 -> 5
        // 3 -> 4
        // 5 -> 4
        // 4 -> 2
        // 4 -> 6
        // 5 -> 2

        // 데이터 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new boolean[N][N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken()) - 1;
            int to = Integer.parseInt(st.nextToken()) - 1;
            board[from][to] = true;
        }

        // floyd warshall 알고리즘 사용
        floydWarshall();

        // [i] 번 학생이 비교 가능한 학생의 수
        // N-1이 되어야 몇 번째인지 알 수 있다.
        int studentResult[] = new int[N];

        // n 번 학생의 정확한 키를 알고 싶다면..
        // [i]행에서 갈 수 있는 학생의 수 == i 학생보다 큰 학생의 수
        // [i]열로 갈 수 있는 학생의 수 == i 학생보다 작은 학생의 수
        // 두 수의 합 == 전체 학생 수 - 1

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == true) {
                    studentResult[i] += 1;
                    studentResult[j] += 1;
                }
            }
        }

        int result = 0;
        for (int student : studentResult){
            if(student==N-1){
                result++;
            }
        }

        System.out.println(result);

        // 자신의 키가 몇 번째인지 알 수 있는 학생이 몇 명인가?

        br.close();
    }}