BOJ) 키 순서 (2458 번)

키 순서

2458번: 키 순서

 

Floyd Warshall

아래는 위키에 설명된 내용을 가져왔다.

플로이드-워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다.[3] 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘[4]과, 스티븐 워셜이 1962년에 발표한 알고리즘[5]과 그래프의 추이적 폐포를 찾는다는 점,[6]그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘(1956년에 발표됨)과 밀접한 관련이 있다는 점에서 동일하다.[7] 이 알고리즘의 삼중 for 반복문의 공식은 1962년에 Peter Ingerman이 설명하였다.[8]이 알고리즘은 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘으로 알려져 있다.

 

키 순서 문제는 가중치가 따로 존재하지 않기 때문에 shortestPath는 아니다.

하지만 i번 학생과 j번 학생이 서로 키가 큰지 작은지 판단할 때, 다른 학생들과의 관계도 이용하기 때문에 플로이드 와샬을 이용해서 문제를 풀 수 있다.

 

 

코드

 

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

public class HeightOrder_2458 {
  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()), m = Integer.parseInt(st.nextToken());
    boolean[][] isTall = new boolean[n+1][n+1];

    while(m-- >0) {
      st = new StringTokenizer(br.readLine());
      int smaller = Integer.parseInt(st.nextToken()), taller = Integer.parseInt(st.nextToken());
      isTall[taller][smaller] = true;
    }

    br.close();
    solution(n, isTall);
  }

  private static void solution(int n, boolean[][] isTall) {
    floydWarshall(n, isTall);
    int[] count = getCountArr(n, isTall);
    int answer = getAnswer(n, count);

    System.out.println(answer);
  }

  private static int getAnswer(int n, int[] count) {
    int answer =0;
    final int MAX = n-1;
    for(int i=1; i<=n; i++) {
      if(count[i] == MAX) {
        answer++;
      }
    }
    return answer;
  }

  private static int[] getCountArr(int n, boolean[][] isTall) {
    int[] count = new int[n+1];

    for(int i=1; i<=n; i++) {
      for(int j=1; j<=n; j++) {
        if(isTall[i][j]) {
          count[i]++;
          count[j]++;
        }
      }
    }
    return count;
  }

  private static void floydWarshall(int n, boolean[][] arr) {
    for(int k=1; k<=n; k++) {
      for (int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
          if(arr[i][k] && arr[k][j]) { // i,k && k,j => i,j
            arr[i][j] = true;
          }
        }
      }
    }
  }
}