[이것이 코딩 테스트다] 정확한 순위
업데이트:
문제
문제의 저작권은 ‘이것이 코딩테스트다’ 교재에 있습니다.
선생님은 시험을 본 학생 N명의 성적을 분실하고, 성적을 비교한 결과의 일부만 가지고 있다. 학생 N명의 성적은 모두 다른데, 다음은 6명의 학생에 대해 6번만 성적을 비교한 결과입니다.
1번 성적 < 5번 성적
3번 성적 < 4번 성적
4번 성적 < 2번 성적
4번 성적 < 6번 성적
5번 성적 < 2번 성적
5번 성적 < 4번 성적
A번 학생의 성적이 B번 학생보다 낮다면 화살표가 A에서 B를 가리키도록 할 때 위의 성적 결과를 다음 그림처럼 표현할 수 있습니다.
이 그림으로 유추해서 순위를 정확히 알 수 있는 학생도 있고, 알 수 없는 학생도 있습니다. 예를 들어 1번 학생은 5번 학생보다 성적이 낮고, 5번 학생은 4번 학생보다 성적이 낮으므로 1번 학생은 4번 학생보다 성적이 낮습니다. 따라서 1번,3번,5번 학생은 모두 4번 학생보다 성적이 낮다고 볼 수 있습니다. 그리고 4번 학생은 2번 학생과 6번학생보다 성적이 낮습니다. 정리하면 4번 학생보다 성적이 낮은 학생은 3명이고, 성적이 높은 학생은 2명이므로 4번 학생의 성적 순위를 정확히 알 수 있습니다. 하지만 예시에서 4번 학생을 제외한 다른 학생은 정확한 순위를 알 수 없습니다. 학생들의 성적을 비교한 결과가 주어질 때, 성적 순위를 정확히 알 수 있는 학생은 모두 몇 명인지 계산하는 프로그램을 작성하세요.
입력 조건
- 첫째 줄에 학생들의 수 N(2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어집니다.
- 다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A, B가 주어집니다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미합니다.
출력 조건
- 첫째 줄에 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력합니다.
입력
6 6
1 5
3 4
4 2
4 6
5 2
5 4
출력
1
접근방식
정확한 성적을 알기 위해서는 모든 학생들과 성적을 비교할 수 있어야 한다.
따라서 입력받은 비교 정보를 가지고 각 학생이 모든 학생들과 성적을 비교할 수 있는지 알기 위해서 플로이드 워셜 알고리즘을 이용하였다.
1)학생들의 비교횟수를 저장할 인접행렬 map을 만든다.
- 자기 자신이면 0, 아니면 INF로 초기화
2)학생들의 비교 정보인 간선정보를 입력받아 1로 표시한다.
3)플로이드 워셜 알고리즘으로 모든 학생들을 탐색하면서 다른 학생에 비교할 수 있는지를map에 기록한다.
4)map을 돌면서 각 학생들의 가로,세로 중 하나라도 비교가능한 경우 카운트한다.cnt==n이 될 경우 전체 학생들을 비교 가능할 수 있으므로 정확한 성적을 알 수 있기 때문에 이 경우 답Ans를 증가시킨다.
import java.io.BufferedReader;
import java.io.*;
import java.util.*;
public class Main {
static final int INF = 1000000000; //INTEGER.MAXVALUE 사용하면 INF+다른값 시 오버플로우 발생
static int n, m; // 학생의 수(정점), 비교횟수(간선)
static int[][] map; // i와 j가 성적 비교할 수 있음을 기록(i성적 < j성적을 의미)
static StringTokenizer st;
static BufferedReader br;
static int Ans; //성적순위 정확히 알 수 있는 학생 수
public static void main(String[] args) throws NumberFormatException, IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n + 1][n + 1];
// 자기 자신이면 0, 아니면 INF로 초기화
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) map[i][j] = ( i == j ) ? 0 : INF;
}
// 간선정보 입력
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken()); // 출발
int e = Integer.parseInt(st.nextToken()); // 도착
map[s][e] = 1; //이 두 학생은 성적 비교 가능함을 표시
}
floyd(); // 플로이드 와샬로 모든 학생들이 다른 모든학생들을 비교할 수 있는지 검사
findAns(); //학생들 행,열을 돌면서 성적순위 정확히 알 수 있는 학생 구하기
}
private static void findAns() {
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++) if(map[i][j] != INF || map[j][i] != INF) cnt++;
if(cnt == n) Ans++; //학생 수만큼 비교가능하면 성적순위 정확히 알 수 있음
}
System.out.println(Ans);
}
private static void floyd() {
for (int k = 1; k <= n; k++) { // 거쳐가는 노드
for (int i = 1; i <= n; i++) { // 출발 노드
for (int j = 1; j <= n; j++) {
map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
}
}
}
}
}