[백준 19538] 루머

문제 링크 => 19538번: 루머 (acmicpc.net)

19538번: 루머

---

BFS 문제이다.

 

노드와 노드는 양방향으로 이어져 있으며 문제에서 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다는 조건을 고려하여 다음 노드로 방문하도록 하는것이 이 문제의 핵심이다.

 

1. 배열 rumor[x] 를 설정하여 다음 노드로 이동할 때 rumor[next]++ 를 해준다. ( next 사람이 루머를 믿는 수를 1 증가시킴) 

 

2. rumor[next] 값( next 사람이 루머를 믿는 수)이 (next 노드가 연결되어 있는 수 + 1 ) / 2 와 같은 경우 즉, 사람의 절반이 루머를 믿게 되는 경우에 해당 노드를 방문처리하도록 하는것이다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> v[200001];
int result[200001];
int rumor[200001];
bool visited[200001];

void init() {
	for (int i = 1; i <= 200000; i++) {
		result[i] = -1;
	}
}

void solve(vector<int> first) {
	priority_queue<pair<int, int> > q;
	for (int i = 0; i < first.size(); i++) {
		q.push({ 0, first[i] });
		visited[first[i]] = true;
		result[first[i]] = 0;
	}
	while (!q.empty()) {
		int cnt = -q.top().first;
		int x = q.top().second;
		q.pop();
		for (int i = 0; i < v[x].size(); i++) {
			int next = v[x][i];
			rumor[next] += 1;
			if (rumor[next] == (v[next].size()+1)/2 && !visited[next]) {
				visited[next] = true;
				q.push({ -(cnt + 1), next });
				result[next] = cnt + 1;
			}
		}
	}
}

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

	init();
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		while (1) {
			int x;
			cin >> x;
			if (x == 0) break;
			v[i].push_back(x);
		}
	}

	vector<int> first;
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		first.push_back(x);
	}
	
	solve(first);

	for (int i = 1; i <= n; i++) cout << result[i] << " ";

	return 0;
}