키순서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		boolean[][] check = new boolean[n][n];
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			check[a][b] = true;
		}
	//플로이드 워셜 알고리즘을 통해서 모든 노드간 관계를 알아낸다. 원래 최단거리를 쓸때 사용하는경우는
// D(i,k) = min(D[i,k], D[i, k] + D[k, j])이다. 
// i는 시작점 j는 도착점 그리고 k는 i와 j사이에 있는 노드들을 의미한다. 
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
				//check i->k i학생이 k보다 작다. 
				//k학생이 j보다 작다?
				// 결국 i는 j보다 작다.
					if(check[i][k] && check[k][j]) {
						check[i][j] = true;
					}
				}
			}
		}
		
		int[] cnt = new int[n];
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
			//노드들을 검사하면서 i가 알 수 있는 관계의 수를 알아낸다.
		//학생 i가 다른 학생 j와 비교가능하면 카운트 증가 
		// cnt[i]는 학생 i가 다른 모든 학생과 비교할 수 있는 관계의 수 그리소 n-1의 값이 들어가게 되면 등수를 정확하게 알 수 있다. 
                if(check[i][j] || check[j][i]) {
					cnt[i] ++;
				}
			}
		}
		//등수를 정확하게 알 수 있는 학생 수를 계산 
		int res =0;
		for(int num : cnt) {
			if(num == n-1) res++;
		}
		System.out.println(res);
		
	}
}

플로이드 워셜을 사용한 풀이...

플로이드 워셜?

• 모든 노드간 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행 가능
• 동적 계획법의 원리 사용
• O(V^3) -> v: 노드

벨만포드?

• 특정 출발 노드에서 다른 모든 노드까지 최단 경로 탐색 가능
• 음수 가중치가 있어도 수행가능
• 전체 그래프에서 음수 사이클의 여부 판단 가능
• O(VE) -? V :노드수 E :엣지수

위의 정리에서 알 수 있듯이 플로이드 워셜과 벨만 포드의 차이는
특정 출발 노드인가 혹은 모든 노드간인가 로 알아볼 수 있다.

위 문제를 풀기위해선 플로이드 워셜의 알고리즘 구조를 어느정도 외우고 있어야한다. 즉 정형적인 풀이 방법이 있다는 의미이다.

자세한 풀이는 주석으로 달아놓았다.

1. 플로이드 워셜 알고리즘으로 서로의 등수를 알 수 있다면 true, false로 표시하기(기본은 false로 표시되어있고 i가 k보다 작은 관계라면 true로 표시), 이때 인접 배열을 통해서 표시하도록 한다.
2. 각 노드(학생 수)마다 등수를 알 수 있는지 찾기
   (check[i][j], check[j][i] )둘 중 하나라도 true라면 등 수를 알 수 있게된다.
3. 노드 등수 배열에 값을 지정했으니 num값이 n-1(노드 -1) 이면 자기 자신 -1이라서 등수를 체크할 수 있는 경우이다!

REVIEW

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL