[알고리즘] 백준 > #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;
}
}
Author And Source
이 문제에 관하여([알고리즘] 백준 > #2458. 키 순서), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/알고리즘-백준-2458.-키-순서저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)