[알고리즘] C++ 백준 2617 구슬 찾기

백준 2617

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

2617번: 구슬 찾기

풀이 전 나의 생각

구슬 간의 무게 관계가 주어질 때, 절대로 무게가 중간이 될 수 없는 구슬을 찾아야 한다.

 

조건

- N(1 ≤ N ≤ 99)

- M(1 ≤ M ≤ N(N-1)/2)

- N은 홀수

 

과정

구슬은 무조건 홀수로 주어지며 중간값은 (N + 1) / 2 라는 것을 알 수 있다.

만약 N이 5라면 중간값은 3이 될 것이고 중간 구슬 보다 가벼운 구슬이

2개, 무거운 구슬이 2개 있어야 한다.

 

여기서 알 수 있는 것은 가벼운 구슬의 개수가 2개보다 적다면 중간값이 될 수 있는 가능성이 있지만

2개보다 많다면 절대 중간값이 될 수 없다는 것이다. 이는 무거운 경우에도 마찬가지다.

 

따라서 중간값이 절대로 될 수 없는 구슬은 현재 선택한 구슬의

더 가볍거나 무거운 구슬의 개수가 (N + 1) / 2보다 같거나 커야한다. 

 

그럼 현재 구슬보다 더 가벼운 구슬과, 무거운 구슬의 개수를 각각 구해주면 될 것이다.

따라서 가벼운 구슬의 개수를 찾아낼 그래프와

무거운 구슬의 개수를 찾아낼 그래프를 제작하여 탐색을 진행해주면 된다.

 

ex) 2가 1보다 무겁다, 4가 2보다 무겁다, 현재 선택 구슬 1

-> (무거운 구슬 그래프) 1 -> 2 -> 4 = 1보다 무거운 구슬은 2와 4인 2개

-> (가벼운 구슬 그래프) 4 -> 2 -> 1 = 1보다 가벼운 구슬은 0개

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>>light(100);
vector<vector<int>>heavy(100);
bool visited[100];

int ans = 0;

//가볍고 무거운 구슬을 찾기 위한 BFS 탐색
int bfs(vector<vector<int>> v, int st)
{
	fill(visited, visited + 100, false);

	visited[st] = true;
	queue<int> q;
	q.push(st);

	int cnt = 0;

	while (!q.empty())
	{
		int now_node = q.front();
		q.pop();

		for (int next : v[now_node])
		{
			if (!visited[next])
			{
				visited[next] = true;
				cnt++;
				q.push(next);
			}
		}
	}	
	
	return cnt;
}

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

	int N, M;
	cin >> N >> M;

	//가볍고 무거운 관계를 각각 저장해준다.
	for (int i = 0; i < M; i++)
	{
		int u, v;
		cin >> u >> v;
		light[u].push_back(v);
		heavy[v].push_back(u);
	}

	for (int i = 1; i <= N; i++)
	{	
		// 구슬의 중간값보다 같거나 크다면 절대로 중간 구슬이 될 수 없기에 최종값을 증가시켜준다.
		if (bfs(light, i) >= (N + 1) / 2 || bfs(heavy, i) >= (N + 1) / 2) ans++;
	}

	cout << ans;
}