[알고리즘] 백준 > #2458. 키 순서

문제링크

백준 #2458. 키 순서

풀이방법

그 학생이 자기 키 순서를 알기 위해선 본인보다 (큰 학생의 수) + (작은 학생의 수) 가 n - 1이어 한다. 그래서 큰 학생의 수, 작은 학생의 수를 구할 방법을 생각했다. 큰 한생의 수는 바로 플로이드와샬을 사용하면 되겠다고 생각했다. 근데 작은 학생의 수는 매번 dfs를 해야하나? 했는데 갑자기 화살표의 방향을 바꾸는게 생각났다. 그래서 학생의 순서를 정방향인 orders와 반대방향인 reversedOrders에 저장했다. 또, 각각에 대한 플로이드와샬을 isReachable과 isReachableReversely에 저장했다. 이는 boolean형 이차원배열로, isReachable[i][j] = isReachable[i][j] || (isReachable[i][s] && isReachable[s][j]); 이런 방식으로 갱신을 진행했다. 그래서 각각을 count한 sum이 n - 1이면 자신의 순서를 아는 학생으로 간주했다. 끝!

코드

class Solution2458 {
    private int n;
    private LinkedList<Integer>[] orders;
    private LinkedList<Integer>[] reversedOrders;

    Solution2458(int n, LinkedList<Integer>[] orders, LinkedList<Integer>[] reversedOrders) {
        this.n = n;
        this.orders = orders;
        this.reversedOrders = reversedOrders;
    }

    int countKnowingStudents() {
        boolean[][] isReachable = new boolean[n + 1][n + 1];
        boolean[][] isReachableReversely = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (Integer next: orders[i]) isReachable[i][next] = true;
            for (Integer prev: reversedOrders[i]) isReachableReversely[i][prev] = true;
        }
        for (int s = 1; s <= n; s++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    isReachable[i][j] = isReachable[i][j] || (isReachable[i][s] && isReachable[s][j]);
                    isReachableReversely[i][j] = isReachableReversely[i][j] || (isReachableReversely[i][s] && isReachableReversely[s][j]);
                }
            }
        }

        int numOfKnowingStudent = 0;
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= n; j++) {
                if (isReachable[i][j]) count++;
                else if (isReachableReversely[i][j]) count++;
            }

            if (count == n - 1) numOfKnowingStudent++;
        }

        return numOfKnowingStudent;
    }
}