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

#2458 키 순서

난이도 : 골드 4

유형 : 그래프 이론 / 플로이드 와샬

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인 학생보다 키가 작은 것을 의미한다.

▸ 출력

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

 

문제 풀이  

그래프 탐색 문제로 플로이드 와샬 알고리즘을 활용하면 해결할 수 있다. 첫 번째로 생각해야 할 부분은 어떤 상황에서 두 학생의 등수를 매길 수 없는가이다. 주어진 예제를 보면 (1,3) 과 (5)의 등수를 매길수 없고, (2)와 (6)을 매길 수 없다. 이 관계를 각 관점에서 살펴보면 서로가 연결되어 있지 않다는 것이다.(역방향 그래프 포함)

 

(3)과 (1,5)의 관계

 

그러나 역방향도 고려하면 4번 학생은 모든 학생들과 연결되어 있음을 알 수 있다. 또한 1번 학생도 3번과 연결되어있다면 마찬가지로 모든 학생들과 연결되게 된다. 

 

4번 예시, 만약 1번학생도 3번과 연결되어있다면 모든 학생과 연결

 

 

따라서 각 노드가 모든 점들과 연결되어 있는지 여부만 체크해주면 답을 구할 수 있기 때문에 이는 모든 정점에서 모든 정점으로의 탐색을 하는 플로이드 와샬 알고리즘을 활용할 것이다. 해당 풀이 로직에서는 모든 정점에서 모든 정점을 탐색하되 최단경로 갱신이 아닌 연결 여부만 체크해 줄 것이다.

 

원래 플로이드 와샬은 가중치 그래프에서 모든 정점의 최단경로를 찾아내기 위해 활용하는 O(n^3)의 시간복잡도를 가지는 알고리즘이다. 해당 문제처럼 최대 500개의 노드를 가진 그래프를 비교하는 것은 1억번의 연산을 넘기 때문에 복잡한 연산이 요구되는 로직에서는 시간초과 발생이 있어 사용하는 것은 위험하다. 그러나 이렇게 간단한 덧셈이나 불린 연산 같은 경우는 가볍게 통과되는 것 같다.

for(int k=0; k<n; k++) { // 중간 지점
	for(int i=0; i<n; i++) { // 시작 지점
		for(int j=0; j<n; j++) { // 도착 지점 
			if(check[i][k] && check[k][j]) { // i->k 연결 && k-> j 연결
				check[i][j] = true;
			}
		}
	}
}

 

연결 여부를 구했으면 이젠 연결된 학생의 수를 카운트해주면 된다. 만약 자신과 연결되어 있는 학생의 수가 자신을 제외한 n-1명이라면 모든 학생과 비교가 가능하다는 뜻이므로 카운트를 해주면 된다. 물론 연결여부는 역방향도 포함이다.

int[] cnt = new int[n];
for(int i=0; i<n; i++) {
	for(int j=0; j<n; j++) {
		// i->j 정방향 || j -> i 역방향
		if(check[i][j] || check[j][i]) { 
			cnt[i] ++;
		}
	}
}

 

설계

1. 모든 정점에서 모든 정점을 탐색하여 연결 여부를 체크한다. if(check[i][k] && check[k][j]) check[i][j] = true;
2. 정방향, 역방향을 탐색하여 각 노드의 연결되어 있는 노드 수를 카운트한다. if(check[i][j] || check[j][i]) cnt[i]++;
3. 만약 연결되어있는 노드의 수가 n-1(자신 제외)이면 모든 학생과 비교가 가능하므로 결과값에 카운트한다. if(num == n-1) res++;
4. 3번에서 카운트한 결과값을 출력한다. 

 

풀이 코드 

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;
		}
		
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; 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++) {
                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);
		
	}
}