백준 2617 c++ "구슬 찾기" -[PlusUltraCode]

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

2617번: 구슬 찾기

[필자 사고]

 

풀이 과정이 다양한 문제이다.

 

BFS 다익스트라 플로이드워셜 DFS 등 여려가지고 존재하고 필자는 플로이드와샬알고리즘을 사용하여 문제를 해결했다.

 

이 문제의 특이한 점은 중앙값에 있다. 중간값을 구하는 공식은 (N+1)/2를 통해 구할수 있고 플로이드 와샬 알고리즘을

 

적용했을 때 1번 경로에서 도달할 수 있는 경로가 중앙값보다 같거나 많으면 중앙값이 될 수 없는 원리이다.

 

이러한 과정만 알고 있으면 쉽게 문제를 해결할 수 있다.

 

 

[필자 사고]

#include <iostream>
#include <vector>

using namespace std;

int N,M;

vector<vector<int>> Arr;
vector<vector<int>> RArr;

int INF = 987654321;
void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	RArr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1, INF);
		RArr[i].resize(N + 1, INF);
	}
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> e >> s;
		Arr[s][e] = 1;
		RArr[e][s] = 1;
	}

}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (s == e)continue;
				if (Arr[s][e] > Arr[s][k] + Arr[k][e]) {
					Arr[s][e] = Arr[s][k] + Arr[k][e];
				}
				if (RArr[s][e] > RArr[s][k] + RArr[k][e]) {
					RArr[s][e] = RArr[s][k] + RArr[k][e];
				}
			}
		}
	}
}



int main(void) {
	Input();
	Floyd_Warshall();
	int wndrks = (N + 1) / 2;
	int Result = 0;
	for (int i = 1; i <= N; i++) {
		int count1 = 0;
		int count2 = 0;
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k] != INF && Arr[i][k] != 0)count1++;
			if (RArr[i][k] != INF && RArr[i][k] != 0)count2++;
		}
		if (wndrks <= count1) {
			Result++;
		}
		if (wndrks <= count2) {
			Result++;
		}
	}
	cout << Result;
}