취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2617 문제인 구슬 찾기이다.
문제는 아래 링크를 확인하자.

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

주어진 구슬들 중, 자신보다 더 무거운게 확실한(주어진 조건들을 이용해 직접 추론 가능한) 구슬의 개수 또는 더 가벼운게 확실한 구슬의 개수가 N의 절반을 넘는 구슬의 개수를 세는 것으로 문제를 해결할 수 있다. 이러한 경우 해당 구슬의 무게가 전체의 중간이 될 수 없음은 자명하다. 그렇지 않은 경우 위상정렬 등을 이용하면 해당 구슬을 가운데 차례에 위치하게끔 하는 방법을 쉽게 얻을 수 있다. (구체적인 방법 서술은 생략한다.)

이를 구하기 위해, 주어진 무게관계들을 이용해 A가 B보다 더 무거움에 대응되는 방향에지로 만들어진 그래프와 A가 B보다 더 가벼움에 대응되는 방향에지로 만들어진 그래프를 만들자. 이 때, 각 그래프에서 어떤 노드 x로부터 다른 노드 y로 가는 경로가 존재한다는 것은 x와 y 사이의 무게 사이에 (그래프의 종류에 따른) 관계가 있음을 의미함을 관찰하자. 따라서 이와 같은 그래프를 이용하면 각 노드에서 이동할 수 있는 노드의 개수를 세는 것으로 문제를 해결할 수 있게 된다.

전체 구슬의 개수가 충분히 적으므로, 해당 값을 구하기 위해 각 노드를 출발점으로 하는 탐색을 일일이 시도하는 것으로도 문제를 충분히 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

int N, M;
vector<int> G1[100], G2[100];
int visited[100];

int func1(int x) {
	memset(visited, 0, sizeof(visited));
	int ret = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G1[cur]) {
			if (visited[nxt]) continue;
			ret++, que.push(nxt);
			visited[nxt] = 1;
		}
	}

	return ret;
}

int func2(int x) {
	memset(visited, 0, sizeof(visited));
	int ret = 0;
	queue<int> que;
	que.push(x);
	visited[x] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G2[cur]) {
			if (visited[nxt]) continue;
			ret++, que.push(nxt);
			visited[nxt] = 1;
		}
	}

	return ret;
}

int ans;

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

	cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		G1[x].emplace_back(y);
		G2[y].emplace_back(x);
	}

	for (int i = 1; i <= N; i++) {
		if (func1(i) > N / 2 || func2(i) > N / 2) ans++;
	}

	cout << ans;
}