[백준 / BOJ] C++ 2617 구슬 찾기

2617번: 구슬 찾기

 

문제

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

2617번: 구슬 찾기

 

 

풀이

N개의 구슬들의 무게를 비교한 정보가 M개 있을 때, 이를 가지고 무게가 중간일 수 없는 구슬의 수를 구하는 문제다.

 

기본적인 개념은 i번 구슬보다 무거운 구슬의 수나 가벼운 구슬의 수가 N/2보다 크면 그 구슬은 중간일 수 없다. 따라서 각 구슬 간의 무게를 모두 비교하기 위해 플로이드-워셜 알고리즘을 사용했다.

 

무게 관계 a, b는 a가 b보다 무겁다는 뜻이므로 dist[b][a] = 1로 해줬다. 플로이드-워셜 알고리즘을 수행한 후 모든 i번 구슬에 대해 나머지 j번 구슬과의 관계를 비교한다.

1. dist[i][j] == 0 이면, 이는 자기 자신과 비교하는 것이므로 넘어간다.
2. dist[i][j] != INF 라면, j번 구슬은 i번 구슬보다 무겁다는 뜻이다. (i번 구슬보다 무거운 구슬의 수 big 1 증가)
3. dist[i][j] == INF 이면서 dist[j][i] != INF 라면, j번 구슬은 i번 구슬보다 가볍다는 뜻이다. (i번 구슬보다 가벼운 구슬의 수 small 1 증가)
4. dist[i][j] == INF 이면서 dist[j][i] == INF 라면, i번 구슬과 j번 구슬을 비교할 수 없다.

small과 big 중 하나라도 N/2보다 크다면, i번 구슬은 중간일 수 없는 구슬이다. 중간일 수 없는 구슬의 개수를 출력하면 된다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, ans = 0, dist[100][100];
  cin >> N >> M;
  // dist 배열 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      dist[i][j] = i == j ? 0 : INF;
  // 구슬 관계 입력
  for (int i = 1; i <= M; i++) {
    int a, b;
    cin >> a >> b;
    // a가 b보다 무겁다
    dist[b][a] = 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]);
  // i번 구슬과 j번 구슬 관계 비교
  for (int i = 1; i <= N; i++) {
    int small = 0, big = 0;
    for (int j = 1; j <= N; j++) {
      // 자기 자신과 비교인 경우
      if (dist[i][j] == 0)
        continue;
      // i번보다 j번이 무거운 경우
      if (dist[i][j] != INF)
        big++;
      // i번보다 j번이 가벼운 경우
      else if (dist[j][i] != INF)
        small++;
    }
    // 중간일 수 없으면
    if (small > N / 2 || big > N / 2)
      ans++;
  }
  cout << ans << '\n';
  return 0;
}