[BOJ] (C++14) 2458번 문제) 키 순서

문제

• 링크
• 누가 누구보다 크다는 키 순서 쌍을 받아오면 이 키 순서 쌍을 토대로 누가 몇번째로 큰지 확실히 알 수 있는 사람의 수

힌트

• 플로이드-워셜 알고리즘을 쓰면 노드에서 다른 노드를 거쳐 가는 길까지 다 구할 수 있다
• 순서를 확실히 알 수 있는 사람: 자기보다 큰 노드의 수 + 자기보다 작은 노드의 수 = 모든 노드의 수 - 1 을 구할 수 있는 사람

플로이드-워셜 알고리즘

 

// vertex가 N개 있을 때
// i부터 j까지 edge의 유/무 및 weight 값은 matrix로 저장됨

// int graph[i][j]가 존재 한다고 가정
for (int k = 0; k < N; k++) {
	for (int i = 0; i < N; i++) {
    	for (int j = 0; j < N; j++) {
        	graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
        }
    }
}

 

 

소스 코드

#include <cstdio>
#include <iostream>

int main() {
  //freopen("input.txt", "r", stdin);

  int N, M;
  std::cin >> N >> M;
  bool** rows;
  rows = new bool* [N];
  for (int i = 0; i < N; i++) {
    rows[i] = new bool [N];
  }
  for (int i = 0; i < M; i++) {
    int from, to;
    std::cin >> from >> to;
    rows[from-1][to-1] = true;
  }

  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if ((rows[i][k] == true) && (rows[k][j] == true)) rows[i][j] = true;
      }
    }
  }

  int answer{0};
  for (int k = 0; k < N; k++) {
    int num{0};
    for (int i = 0; i < N; i++) {
      if ((i != k) && ((rows[i][k] == true) || (rows[k][i] == true))) {
        num++;
      }
    }
    if (num == (N-1)) answer++;
  }
  std::cout << answer << std::endl;
  return EXIT_SUCCESS;
}