c언어 2617번 구슬 찾기 (백준)

#include <stdio.h>
#define INF 100000000

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);
	int d[n][n];
	
	for(int i=0; i<n; i++) { //그래프 배열 초기화
		for(int j=0; j<n; j++) d[i][j] = INF;
	}
	
	while(m--) { //간선 입력
		int a, b;
		scanf("%d %d", &a, &b);
		d[a-1][b-1]=1; //단방향, a>b 라는 의미
	}
	
	for(int k=0; k<n;k++) //Floyd Warshall
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++) {
		if(d[i][k]+d[k][j] < d[i][j])
		d[i][j] = d[i][k]+d[k][j];
	}
	
	int ans = 0;
	for(int i=0; i<n; i++) { //확실하게 구별 가능한지
		int big = 0;
		int small = 0;
		for(int j=0; j<n; j++) { 
			if(d[i][j] < INF) big++; //크다!
			if(d[j][i] < INF) small++; //작다!
		}
		if(big > n/2) ans++; //n/2 초과면 확실히 중앙이 아님을 알 수 있다.
		if(small > n/2) ans++;
	} printf("%d", ans);
}

풀이 : Floyd Warshall

0. n,m  입력 받음

1. 그래프 배열 초기화

2. 간선 입력 //단방향이다. d[a][b] = 1는 a>b라는 의미이다.

3. Floyd Warshall76

4. 크다 ([비교하는 것][나머지] = 1) 또는 작다 ([나머지][비교하는 것] = 1) 의 개수를 구한다

5. 크다 나 작다 의  개수가 n/2초과라면 확실히 중앙이 아님을 알 수 있다.

6. n/2 초과시 ans을 1 증가 한다.

7. ans을 출력한다.

 

n/2 초과시 확실히 가운데가 아님을 알 수 있는 이유

n은 반드시 홀수이며, n/2의 초과는 n의 과반수이므로, 확실히 가운데가 아니다.

 

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

2617번: 구슬 찾기