[백준] 2458. 키 순서 (Java)

 

문제

2458번: 키 순서

 

알고리즘

그래프, 플로이드 워셜(Floyd Warshall) 알고리즘

 

 

풀이

자신의 키가 몇 번째인지 알기 위해서는

자신보다 키가 작은 학생이 몇 명인지, 키가 큰 학생이 몇 명인지 알아야한다.

 

자신보다 키가 작은 학생은 그래프 상에서 [i][j]로,

자신보다 키가 큰 학생은 그래프 상에서 [j][i]로 표현될 수 있다.

 

예를 들어 예제 그림에서처럼

5번 학생이 4번 학생보다 키가 작다는 것을 graph[5][4] = true 로 표현한다면

6번 학생이 4번 학생보다 키가 크다 = 4번 학생이 6번 학생보다 크기 작다 => graph[4][6] = true가 될 것이다.

 

이런 식으로 4번 학생은

graph[1][4] = true

graph[5][4] = true

graph[3][4] = true

graph[4][6] = true

graph[4][2] = true 로

자신을 제외한 다른 모든 학생과 연결(graph[i][j] || graph[j][i]) 관계이기 때문에 자신이 몇 번째 학생인지 알 수 있는 것이다.

 

하지만 graph[1][4] 처럼 직접적으로 연결되어있지 않은 학생들의 관계를 파악해야하는데

이를 위해서 플로이드 워셜 알고리즘을 사용한다.

 

플로이드 워셜 알고리즘을 사용하면

graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]) 로 표현할 수 있는데

이는 i번째 학생이 k번째 학생보다 키가 작고 k번째 학생이 j번째 학생보다 키가 작다면

i번째 학생은 j번째 학생보다 키가 작다는 것이다.

 

따라서 플로이드 워셜 알고리즘으로 모든 학생들 간의 연결 관계를 파악하고

다른 모든 학생들과 연결되어있는 학생의 수를 출력한다.

 

 

 

코드

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 NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		boolean[][] graph = new boolean[N + 1][N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			graph[a][b] = true;
		}

		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);

		int ans = 0;
		label1: for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j) continue;
				if (!graph[i][j] && !graph[j][i]) continue label1;
			}
			ans++;
		}

		System.out.println(ans);
	}
}