[백준 / BOJ] C++ 2458 키 순서

2458번: 키 순서

 

문제

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

2458번: 키 순서

 

 

풀이

학생들 간 키를 비교해 자신이 몇 번째인지 알 수 있는 학생의 수를 구하는 문제다. 플로이드-워셜 알고리즘을 사용해 주어진 간선은 1, 나머지는 INF로 두고 플로이드-워셜을 돌린다.

 

정점 u, v의 키를 비교할 때 dist[u][v]가 INF가 아니라면 u보다 v가 키가 큰 것이고

dist[v][u]가 INF가 아니라면 v보다 u가 키가 큰 것이다.

둘 다 아니라면 비교를 할 수 없다.

 

즉, 1부터 N까지 모든 정점에 대해 자신이 아닌 다른 점까지 도달할 수 있거나 다른 점에서 자신까지 도달할 수 있는 경우의 수를 세면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, dist[501][501], cnt = 0;
  cin >> N >> M;
  // dist 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      dist[i][j] = INF;
  // 간선 입력
  while (M--) {
    int a, b;
    cin >> a >> b;
    dist[a][b] = 1;
  }
  // 플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  // 모든 정점 검사
  for (int i = 1; i <= N; i++) {
    int flag = 1;
    for (int j = 1; j <= N; j++) {
      // 자기 자신에 방문해야 하는 경우
      if (i == j)
        continue;
      // 자기 자신에서 다른 점으로, 다른 점에서 자기 자신으로 모두 불가능한 경우
      if (dist[i][j] == INF && dist[j][i] == INF) {
        flag = 0;
        break;
      }
    }
    // 한 번이라도 자신이 다른 점에 도달하거나 자기 자신으로 도달할 수 있는 점이 없는 경우
    if (flag)
      cnt++;
  }
  cout << cnt << '\n';
  return 0;
}