[코테] 백준 2458번 : 키 순서 (java)

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

알고리즘 분류 : 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 최단 경로, 플로이드–워셜

❓문제

---

🔅해석

모든 학생의 키를 비교한 횟수를 알아야하기 때문에 전체 쌍의 계산이 필요한 "플로이드-워셜" 알고리즘을 사용한다.

 

1. 거리 초기화 
만약 두 정점 간에 직접 연결된 간선이 있다면 그 가중치로 초기화하고, 연결되어 있지 않다면 무한대(또는 매우 큰 값)로 설정한다. 자신에게 가는 거리는 0으로 설정한다.

for (int n = 1; n <= N; n++) {
    Arrays.fill(map[n], INF);
    map[n][n] = 0;
}

 

2. 동적 프로그래밍(DP) 적용
각 정점을 중간 정점으로 고려하여, 다른 모든 정점 쌍에 대해 최단 경로를 갱신한다. 즉, 정점 k를 중간 정점으로 사용하는 경우, i에서 j로 가는 경로가 i -> k -> j로 더 짧아질 수 있는지 확인하고, 그렇다면 경로를 갱신한다.

private static void floyd() {
    for (int k = 1; k <= N; k++) {
        for (int a = 1; a <= N; a++) {
            for (int b = 1; b <= N; b++) {
                if (a == b)
                    continue;
                if (map[a][k] == INF || map[k][b] == INF)
                    continue;

                map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
            }
        }
    }
}

 

3. 결과 출력 

결과를 출력해보면 위와 같은 테이블이 나온다.

행을 보면 해당 행보다 큰 학생의 수를 알 수 있고, 열을 보면 해당 열보다 작은 학생의 수를 알 수 있다.

자신보다 큰 학생과 작은 학생의 수가 N - 1(자기자신) 와 일치한다면 자신의 키 순서를 알 수 있는 학생이다.

---

⭕정답 코드

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

public class Main {
	
	static final int INF = Integer.MAX_VALUE;
	
	static int N, M;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
	
		map = new int[N + 1][N + 1];
		
		for (int n = 1; n <= N; n++) {
			Arrays.fill(map[n], INF);
			map[n][n] = 0;
		}
		
		// map 생성
		int a, b;
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			
			map[a][b] = 1;
		}
		
		floyd();
		
		int answer = 0;
		for (int i = 1; i <= N; i++) {
			int count = 0;
			for (int j = 1; j <= N; j++) { 
				if (i == j) continue;
				
				if (map[i][j] != INF || map[j][i] != INF) {
					count++;
				}
			}
			// 자기자신을 제외한 N-1개의 노드와 키순서를 알면 자신의 키가 몇번째인지 알 수 있다.
            if(count == N-1){
                answer++;
            }
		}
		System.out.println(answer);
		
		br.close();
	}

	private static void floyd() {
		
		for (int k = 1; k <= N; k++) {
			for (int a = 1; a <= N; a++) {
				for (int b = 1; b <= N; b++) {
					if (a == b) continue;
					if (map[a][k] == INF || map[k][b] == INF) continue;
					
					//if (k == a || k == b) continue;
					map[a][b] = Math.min(map[a][b], map[a][k] + map[k][b]);
				}
			}
		}
	}

}

 

---

❗결과