[백준 2617] 구슬 찾기 (C++)

이 문제는 입력으로 구슬의 무게 관계가 주어진다. 이렇듯 관계를 표현하는 데 효과적인 자료구조는 그래프이므로, 그래프로 접근하는 것이 좋다.

그래프의 표현은 인접 행렬과 인접 리스트로 표현이 가능한데, 시간 복잡도와 공간 복잡도가 $O(V + E)$로 뛰어난 인접 리스트로 표현할 것이다.

이때, 해당 정점보다 무게가 무거운 것과 가벼운 것이 몇 개씩 존재하는지 갯수를 세어, 둘 중 하나라도 (n + 1) / 2보다 크거나 같은 것이 있다면, 무게가 전체의 중간이 될 수 없을 것이다.

중간이 되려면, 정렬했을 때 (n + 1) / 2번째 정점이 되어야하는데, 그렇다면 왼쪽과 오른쪽에 (n + 1) / 2 - 1개의 정점이 있을 것이기 때문에, 무게가 무겁거나 가벼운 것의 갯수가 (n + 1) / 2보다 크거나 같은 것이 있으면, 중간이 될 수 없다는 의미가 된다.

그렇다면, 각 정점에서 해당 정점보다 가벼운 것과 무거운 것의 갯수를 세어줘야 한다.

우리는 시작 정점에서 무게가 증가하는 순으로 방문한다면, 시작점을 제외한 나머지 방문 정점들은 최소한 시작 정점보다는 무겁다는 사실을 쉽게 알 수 있다. 그리고, 시작 정점은 다른 방문 정점들의 수만큼 무게가 무거운 정점이 존재함을 알 수 있다.

따라서, 우리는 모든 정점에 대해서 BFS를 적용해 그래프를 탐색하고 시작 정점 st는 정점을 이동해나갈 때마다, st정점보다 무거운 정점의 갯수인 cnt[st][1]을 1씩 증가시켜 주고, 이동할 다음 정점인 nxt에 대해, nxt정점보다 가벼운 정점 갯수인 cnt[nxt][0]을 1씩 증가시켜주면 된다.

$1$ ~ $N$의 모든 정점에 대해서 BFS가 적용되므로 각 정점보다 가볍거나 무거운 정점의 갯수를 빠짐없이 셀 수 있다.

이에 대한 시간 복잡도는 $O(99(V + E))$로 1초 이내에 연산이 완료된다.

이를 코드로 옮기면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> adj[100]; // 각 구슬들의 대소관계가 주어졌을 때, 그래프로 표현
int cnt[100][2]; // 각 구슬마다 가볍고, 무거운 다른 구슬들을 갯수를 관리

void bfs(int st) {
	queue<int> q;
	bool vis[100] = {};

	q.push(st);
	vis[st] = 1;

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

		for (int nxt : adj[cur]) {
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = 1;
			cnt[st][1]++;
			cnt[nxt][0]++;
		}
	}
}

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

	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		adj[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) bfs(i);

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (max(cnt[i][0], cnt[i][1]) >= (n + 1) / 2) ans++;
	}
	cout << ans;
}

물론, 모든 정점을 방문해가며 세는 것이기 때문에 DFS로 구현해도 동일한 결과가 나온다.

또 다른 풀이로는 무게가 무거운 관계와 가벼운 관계를 각각 다른 그래프로 관리하면, 두 그래프에 대해 BFS로 탐색했을 때, 각 시작 정점 st에서 무거운 정점의 수와 가벼운 정점의 수를 구해낼 수 있다.

즉, 정점 $V$보다 무거운 정점들을 heavy로, 가벼운 정점들을 light로 관리한다면, 각 그래프를 BFS로 탐색했을 때 heavy를 통해서는 무거운 것들의 갯수, light를 통해서는 가벼운 것들의 갯수를 알 수 있다는 것이다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> heavy[100], light[100];
bool vis[100];

bool bfs(int st, vector<int> (&adj)[100]) {
	fill(vis, vis + n + 1, 0);
	queue<int> q;
	int cnt = 0;

	q.push(st);
	vis[st] = 1;

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

		for (int nxt : adj[cur]) {
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = 1;
			cnt++;
		}
	}

	return cnt >= (n + 1) / 2;
}

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

	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		heavy[v].push_back(u);
		light[u].push_back(v);
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (bfs(i, heavy) || bfs(i, light)) ans++;
	}
	cout << ans;
}