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

링크 : https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

문제 설명 : 

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다. 

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다. 

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

 

입력 : 

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

 

출력 : 

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

 

예제 입력 : 

6 7
1 3
1 5
3 4
5 4
4 2
4 6
5 2

 

예제 출력 : 

2

 

접근법 : 

1) 어떻게 풀 것인가?

N이 500으로 매우 작은 편이다. 

모든 N에 대해서 다른 N-1에 대한 모든 대소비교가 가능한지를 파악해야한다.

 

즉, 1번 학생도 자신과 2~N번까지 모든 학생과 키 비교가 가능한지 파악해야하고,

2번 학생도 1, 3~N번까지 모든 학생과 키 비교가 가능한지 파악해야한다.

이렇게 N번의 학생에 대해 매번 연산을 할 경우 시간초과가 발생한다.

 

그래서, 모든 학생들이 서로 키를 비교할 수 있는지, 모든 경로를 빠르게 한 번에 구해놓고 나서,

1~N번의 학생을 보면서 가능한지만 체크해야한다.

 

이럴 때 사용할 수 있는 알고리즘이 플로이드 워셜 알고리즘이다.

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

 

플로이드 워셜 알고리즘을 요약하면 

N^3의 3중 for문을 돌면서

현재 갖고 있는 (출발지 - 도착지)의 최단경로 값이 빠른지,

(출발지 - 경유지) + (경유지 - 도착지)의 최단경로 값이 빠른지 비교하는 알고리즘이다.

 

// 플로이드-워셜 : 경유지 - 출발지 - 도착지 3중 for문
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}			
		}

 

즉, N^3으로 모든 경우의 수를 체크하면서 최단 경로를 갱신하게 된다. 

이렇게 되면 최종적으로 dist[출발지][목적지]의 값은 최솟값임을 보장하게 된다.

 

최단경로에 주로 쓰이는 플로이드-워셜을 활용하면, 

순서의 비교가 가능/불가능한지 응용할 수 있다. 

(자세한 내용은 아래 코드 참고)

 

 

2) 시간복잡도

플로이드 워셜은 N^3의 시간복잡도를 갖는다.

500^3 = 125,000,000 으로 엄격한 시간복잡도를 갖는 문제에서는

시간초과가 발생할수도 있으나 이번 문제의 경우 큰 무리 없었다.

 

일반적으로 Algorithm 문제 풀이에서 N이 500이하인 경우에만

플로이드 워셜이 가능하다. ( 일부 기업 알고리즘 테스트에서는 N이 300이하인 경우 가능 )

(Java 기준 -  776ms)

 

3) 공간복잡도

N이 500이므로 2차원 배열을 선언해도 크지 않아 특별히 고려하지 않음.

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

플로이드 워셜 활용법 ( 모든 경로를 파악할때, 모든 대소비교가 필요할때 )

 

Java 코드 : 

import java.io.*;
import java.util.*;


// 백준 2458 키순서
public class Main {
	
	static int N, M;					// N : 학생의 수  /  M : 연산의 수 
	static int a, b;  					// input 받는 학생 a, b 
	static int[][] dist;				// floyd-warshall을 위한 2차원 배열
	static final int INF = 999999999;	// 초기화를 위한 불가능한 최댓값
	static int ans;						// 출력할 정답
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 1. 2차원 배열에 INF (최댓값)으로 초기화
		dist = new int [N+1][N+1];
		for (int i=1; i<=N; i++) {
			for (int j=1; j<=N; j++) {
				dist[i][j] = INF;
			}
		}
		
		// 2. 입력 : a - b 학생의 키 순서를 아는 경우 1로 거리 배열 입력
		for (int i = 1; i<= M; i++) {
			st = new StringTokenizer(br.readLine());
			
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());

			dist[a][b] = 1;
		}
		
		// 3. 특정 학생이 모든 학생과의 거리를 체크해야하므로 플로이드 워셜 수행
		// 플로이드-워셜 : 경유지 - 출발지 - 도착지 3중 for문
		for (int k = 1; k <= N; k++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					// dist[i][j]보다 작은 값 나올 경우 갱신
					dist[i][j] = dist[i][j] <= dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];
				}
			}			
		}

		// 4. 모든 학생과의 비교가 가능한 경우
		//    → 거리가 INF 가 아닌 학생의 수가 N-1인 경우 : 키가 몇번째인지 알 수 있으므로 ans++ 
		ans = 0;
		for (int i = 1; i<=N; i++) {
			int cnt = 0;
			for (int j=1; j<=N; j++) {
				if (dist[i][j] != INF || dist[j][i] != INF ) cnt++;
			}
			if (cnt == N-1) ans++;
		}
		bw.write(String.valueOf(ans));
				
		bw.flush();
		br.close();
		bw.close();
	}
	
}