학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.
이 말을 쉽게 생각해보자. 자신의 키를 알 수 있는 경우는 무엇일까? 자신에 앞에 얼마나 있는지 그리고 자신의 뒤에 얼마나 있는지를 아는 사람이 자신이 몇 번째 인지 알것이다!
즉 내가 가거나 나한테 오는 노드들의 수들의 합이 N-1이면 되는 것이다.
만약 갈 수 없는 노드가 나한테 올 수 없다면 그 노드와의 우위를 정할 수 없게 되기 때문에 순위를 알 수 없게 된다.
이 문제를 플로이드 워샬 문제로 해결해보자
노드가 다른 노드에 갈 수 있다면 몇 번째로 가는지를 적도록 하였습니다.
그리고 만약 나한테 오는 노드라면 0으로 기록하도록 하였습니다.
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
mat[a][b] = 1;
mat[b][a] = 0;
}
입력시 코드로 다음과 같이 나보다 몇명 거쳐서 갈 수 있는지를 적습니다.
그리고 반대의 경우는 0으로 기록!
이제 갈 수 있는 모든 경우와 받는 경우를 기록하기 위해 플로이드 워샬을 사용해봅시다.
for(int k=1; k<=N; k++) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(mat[i][j]==0 || mat[i][k]==0 || mat[k][j]==0)
continue;
if(mat[i][j] > mat[i][k] + mat[k][j]) {
mat[i][j] = mat[i][k] + mat[k][j];
mat[j][i] = 0;
}
}
}
}
이를 통해서 우리가 갈 수 있는 경우들을 모두 찾아보고 만약 올 수 있는 경우는 0으로 명시하였습니다.
다음과 같이 입력에 대하여 갈수 있는 경우와 오는 경우를 체크 하였습니다.
501을 최댓값으로 계산하였기에 mat[i][j]가 501인 경우는 i에서 j를 비교하여 우위를 알 수 없음을 보여줍니다.
int count = 0;
for(int i=1; i<=N; i++) {
boolean check = true;
for(int j=1; j<=N; j++) {
if(mat[i][j]==501) {
check = false;
break;
}
}
if(check)
count++;
}
이를 통해 노드들에 어느 정도로 갈 수 있는지를 기록 할 수 있습니다.
문제 해결!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class No2458 {
static int N;
static int[][] mat;
public static void main(String[] args) throws IOException {
input();
pro();
}
private static void pro() {
for(int k=1; k<=N; k++) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(mat[i][j]==0 || mat[i][k]==0 || mat[k][j]==0)
continue;
if(mat[i][j] > mat[i][k] + mat[k][j]) {
mat[i][j] = mat[i][k] + mat[k][j];
mat[j][i] = 0;
}
}
}
}
int count = 0;
for(int i=1; i<=N; i++) {
boolean check = true;
for(int j=1; j<=N; j++) {
if(mat[i][j]==501) {
check = false;
break;
}
}
if(check)
count++;
}
System.out.println(count);
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
mat = new int[N + 1][N + 1];
for(int i=1; i<=N; i++) {
Arrays.fill(mat[i], 501);
mat[i][i] = 0;
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
mat[a][b] = 1;
mat[b][a] = 0;
}
br.close();
}
}