[백준/boj] 2458: 키 순서 (Java) / 플로이드 와샬

문제

2458번: 키 순서

풀이1 : 플로이드 와샬

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

public class Main_BOJ_2458_키순서 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] minEdge;
	static int N, M;
	static int INF = 501;

	public static void main(String[] args) throws Exception {
		int answer = 0;

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

		minEdge = new int[N][N];
		for (int i = 0; i < N; i++)
			Arrays.fill(minEdge[i], INF);

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken()) - 1;
			int to = Integer.parseInt(st.nextToken()) - 1;
            // 
			minEdge[from][to] = 1;
		}

		for (int k = 0; k < N; k++) { // 경유지
			for (int i = 0; i < N; i++) { // 출발지
				for (int j = 0; j < N; j++) { // 도착지
					if (k == i || i == j || k == j)
						continue;
					minEdge[i][j] = Math.min(minEdge[i][j], minEdge[i][k] + minEdge[k][j]);
				}
			}
		}

		for (int i = 0; i < N; i++) {
			boolean flag = true;
			for (int j = 0; j < N; j++) {
				if (i == j || minEdge[i][j] != INF || minEdge[j][i] != INF)
					continue;
				flag = false;
				break;

			}
			if (flag)
				answer++;
		}
		System.out.println(answer);
	}
}

 

• input을 모두 받아온 후, minEdge[i][j] 에는 i학생이 j 학생보다 작다면 1이 담겨져 있다. (그렇지 않다면 INF가 담겨져 있다)
• 경유지 출발지 도착지로 3중 for문을 실행하는 부분이 플로이드 와샬 코드이다.

바로 출발지에서 도착지로 가는 것과, 출발지 -> 경유지 -> 도착지 순으로 가는 방법 중 더 가까운 값을 할당하는 코드이다. 주로 최단거리를 구할 때 쓰이는 코드이지만, 이 문제에서는 i학생이 바로 j학생 키를 알 수 있거나, i학생이 k학생을 통해 j학생의 키를 알 수 있는지를 체크하기 위해 사용됐다. 

• 그 아래 이중 for문은 i 가 자신의 키가 몇 번째인지를 알 수 있는지 확인하는 코드이다. minEdge[i][j] 가 INF 가 아니라는 것은 i가 j보다 키가 작다는 것을 의미하고, minEdge[j][i]가 INF가 아니라는 것은 i가 j보다 키가 크다는 것을 의미한다. 하나라도 INF 라는 것은 i와 j의 키를 비교할 수 없다는 것을 의미하므로, 이 학생은 자신의 키가 몇 번째인지 알 수 없다는 것을 뜻하게 된다.