[백준 10159] 저울 (C#, C++) - soo:bak

문제 링크

10159번 - 저울

설명

일부 물건 쌍의 무게 비교 결과가 주어질 때, 각 물건에 대해 비교 결과를 알 수 없는 물건의 수를 구하는 문제입니다.

접근법

1번이 2번보다 무겁고 2번이 3번보다 무겁다면, 직접 비교하지 않아도 1번이 3번보다 무겁다는 것을 알 수 있습니다. 이처럼 중간 물건을 거쳐 유추할 수 있는 관계를 모두 찾아야 합니다.

두 물건 사이의 관계를 이차원 배열에 저장합니다. 앞 물건이 뒤 물건보다 무거우면 1, 가벼우면 -1, 아직 모르면 0으로 표시합니다. 처음에는 직접 비교한 쌍만 1이나 -1로 채워집니다.

플로이드 워셜 알고리즘을 적용합니다. 모든 물건을 중간 다리로 삼아 관계를 확장해나갑니다. 만약 물건 A가 물건 K보다 무겁고, 물건 K도 물건 B보다 무겁다면, A는 B보다 무겁습니다. 반대로 A가 K보다 가볍고 K도 B보다 가볍다면, A는 B보다 가볍습니다. 이런 식으로 같은 방향의 관계가 연결되면 새로운 관계를 알 수 있습니다.

이 과정이 끝난 후, 각 물건에 대해 관계가 여전히 0인 다른 물건의 수를 세면 그것이 비교 결과를 알 수 없는 물건의 수입니다.

---

Code

C#

using System;

class Program {
  const int MAX = 101;

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var m = int.Parse(Console.ReadLine()!);
    var adj = new int[MAX, MAX];

    for (var i = 0; i < m; i++) {
      var parts = Console.ReadLine()!.Split();
      var a = int.Parse(parts[0]);
      var b = int.Parse(parts[1]);
      adj[a, b] = 1;
      adj[b, a] = -1;
    }

    for (var k = 1; k <= n; k++)
      for (var i = 1; i <= n; i++)
        for (var j = 1; j <= n; j++)
          if (adj[i, k] != 0 && adj[i, k] == adj[k, j])
            adj[i, j] = adj[i, k];

    for (var i = 1; i <= n; i++) {
      var unknown = n - 1;
      for (var j = 1; j <= n; j++)
        if (adj[i, j] != 0) unknown--;
      Console.WriteLine(unknown);
    }
  }
}

C++

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

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

  const int MAX = 101;
  int n, m; cin >> n >> m;
  int adj[MAX][MAX] = {0};

  for (int i = 0; i < m; i++) {
    int a, b; cin >> a >> b;
    adj[a][b] = 1;
    adj[b][a] = -1;
  }

  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (adj[i][k] && adj[i][k] == adj[k][j])
          adj[i][j] = adj[i][k];

  for (int i = 1; i <= n; i++) {
    int unknown = n - 1;
    for (int j = 1; j <= n; j++)
      if (adj[i][j]) unknown--;
    cout << unknown << "\n";
  }

  return 0;
}