[백준 2458] 키 순서 (C#, C++) - soo:bak

문제 링크

2458번 - 키 순서

설명

학생들의 키 비교 결과가 주어지는 상황에서, 학생의 수 N (2 ≤ N ≤ 500), 키 비교 횟수 M, 그리고 각 비교 결과(a번 학생이 b번 학생보다 키가 작음)가 주어질 때, 자신의 키 순서를 정확히 알 수 있는 학생이 몇 명인지 구하는 문제입니다.

자신의 키 순서를 안다는 것은 자신보다 키가 큰 학생과 작은 학생을 모두 파악할 수 있어야 함을 의미합니다. 즉, 자신을 제외한 모든 학생과의 키 대소 관계가 직접 또는 간접적으로 결정되어야 합니다.

접근법

직접 비교 결과만으로는 부족하고, 간접적인 관계도 파악해야 합니다. 예를 들어 A < B이고 B < C라면 A < C임을 알 수 있습니다.

이러한 간접 관계를 모두 찾기 위해 플로이드-워셜(Floyd-Warshall) 알고리듬을 사용합니다.

비교 결과를 인접 행렬로 저장합니다. adj[i][j]가 참이면 i번 학생이 j번 학생보다 키가 작다는 의미입니다.

k번 학생을 중간 매개로 하여, i < k이고 k < j인 경우 i < j 관계를 추가합니다. 모든 학생 k에 대해 이 과정을 반복하면 모든 간접 관계가 추론됩니다.

각 학생에 대해 다른 모든 학생과의 관계를 확인합니다. 어떤 학생 j에 대해 adj[i][j]도 거짓이고 adj[j][i]도 거짓이면 i와 j의 키 대소 관계를 알 수 없습니다. 모든 다른 학생과 관계가 결정된 학생만 자신의 순서를 알 수 있습니다.

세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(N³)이며, N이 최대 500이므로 충분히 빠릅니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var input = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var n = input[0];
      var m = input[1];

      var graph = new bool[n, n];
      for (var i = 0; i < m; i++) {
        var comparison = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var shorter = comparison[0] - 1;
        var taller = comparison[1] - 1;
        graph[shorter, taller] = true;
      }

      for (var k = 0; k < n; k++) {
        for (var i = 0; i < n; i++) {
          if (!graph[i, k]) continue;
          for (var j = 0; j < n; j++) {
            if (graph[k, j])
              graph[i, j] = true;
          }
        }
      }

      var count = 0;
      for (var i = 0; i < n; i++) {
        var canDetermine = true;
        for (var j = 0; j < n; j++) {
          if (i == j) continue;
          if (!graph[i, j] && !graph[j, i]) {
            canDetermine = false;
            break;
          }
        }
        if (canDetermine) count++;
      }

      Console.WriteLine(count);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<bool> vb;
typedef vector<vb> vvb;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vvb graph(n, vb(n, false));

  for (int i = 0; i < m; i++) {
    int shorter, taller;
    cin >> shorter >> taller;
    shorter--; taller--;
    graph[shorter][taller] = true;
  }

  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      if (!graph[i][k]) continue;
      for (int j = 0; j < n; j++) {
        if (graph[k][j])
          graph[i][j] = true;
      }
    }
  }

  int count = 0;
  for (int i = 0; i < n; i++) {
    bool canDetermine = true;
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      if (!graph[i][j] && !graph[j][i]) {
        canDetermine = false;
        break;
      }
    }
    if (canDetermine) count++;
  }

  cout << count << "\n";
  
  return 0;
}