풀이

아이디어

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

이 말을 쉽게 생각해보자. 자신의 키를 알 수 있는 경우는 무엇일까? 자신에 앞에 얼마나 있는지 그리고 자신의 뒤에 얼마나 있는지를 아는 사람이 자신이 몇 번째 인지 알것이다!

즉 내가 가거나 나한테 오는 노드들의 수들의 합이 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();		
	}
}