[알고리즘] 백준 2617번: 구슬 찾기 (C++)

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

2617번: 구슬 찾기

자기 자신보다 구슬이 무거운 것이 몇 개 있는지 혹은 가벼운 것이 몇 개 있는지 파악하여 둘 중에 하나가 (n + 2) + 1보다 크거나 같으면 절대 전체의 중간에 있지 않다는 것을 알 수 있다.

 

그렇다면 어떻게 파악하는가? 플로이드 와샬을 쓰면 된다.

무거운 구슬 가벼운 구슬 순서대로 m개 주어졌을 때

가벼운 구슬에서 무거운 구슬로 가는 경로를 1이라고 설정해주고 나서

플로이드 와샬을 돌려주면 예를 들어 1이라는 구슬에서 2라는 구슬에 갈 때의 경로가 INF라면 1과 2 사이의 관계를 알 수가 없다. 하지만, INF가 아니라면 1과 2 사이의 무계 관계를 파악할 수 있다는 뜻이다.

#include <iostream>
#include <vector>
#define MAX 99 + 1
#define INF 987653421
using namespace std;

int graph[MAX][MAX];
int dist[MAX][MAX];

int n, m;

void floydWarshall() {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) continue;
				if (graph[i][k] + graph[k][j] < graph[i][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

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

	floydWarshall();
	int result = 0;

	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		int cnt2 = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			if (graph[i][j] != INF) {
				//cout << "무거운 거" << '\n';
				//cout << i << ' ' << j << '\n';
				cnt++;
			}
			if (graph[j][i] != INF) {
				//cout << "가벼운 거" << '\n';
				//cout << j << ' ' << i << '\n';
				cnt2++;
			}
		}
		//cout << cnt << ' ' << cnt2 << '\n';
		if (cnt >= (n / 2) + 1 || cnt2 >= (n / 2) + 1) {
			result++;
		}
	}

	cout << result;
	return 0;
}