[백준/알고리즘] 19541번 루머 (골드 4)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 19541번

백준 19538번 문제

 

풀이 알고리즘 : BFS

 

UCPC 2020 예선 G번 문제인 루머 문제입니다.

한 노드를 봤을 때, 연결된 인접 노드의 절반 이상이 루머를 믿고있다면, 해당 노드도 루머를 믿게 되고, 노드별로 루머를 믿게 된 시간을 출력하는 문제입니다.

 

여러가지 방법이 있겠지만, 저는 Queue를 두개 이용하여 BFS를 통해 해결했습니다.

queue<pii> q, qq로 선언을 하였고, 다음과 같이 사용하였습니다.

q : "루머를 믿고 있는" 노드번호, 현재 시간을 저장

qq : "q에서의 노드에 인접한" 노드번호, 현재 시간을 저장

 

먼저 q에 최초 루머를 믿고 있는 노드번호와 시간 0을 입력합니다.

while(!q.empty()) 안에는 두개의 while문이 있는데,

 

첫번째 while문에서는, 현재 q에 들어있는 루머를 믿고 있는 노드의 인접 노드를 확인하여, 해당 인접 노드의 주위에 루머를 믿는 노드의 개수를 1 증가시키고, qq에 push 하는 역할을 합니다.

 

두번째 while문에서는, 위에서 qush한 인접 노드들을 하나 하나 확인하고, 만약 "인접한 루머 노드 개수 * 2 >= 인접 노드 개수"가 된다면, 해당 노드는 루머를 믿게 되므로 다시 q에 push합니다.

 

위의 과정을 반복하면, 더이상 루머를 전파할 수 없다면 q가 비게 되어 반복문을 탈출하고, 마지막에 check배열에 저장한 시간들을 출력하면 됩니다.

 

아래는 제출코드입니다.

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// int pair 간단히
#define pii pair<int, int>
#define mp(X, Y) make_pair(X, Y)

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n;
	queue<pii> q, qq;
	vector<int> adj[n + 1];
	vector<int> check(n + 1, -1);
	vector<pii> nearnode(n + 1, mp(0, 0));

	for(int i = 1; i <= n; i++) {
		int num;
		while(true) {
			cin >> num;
			if(!num) break;
			else {
				nearnode[i].first++;
				adj[i].push_back(num);
			}
		}
	}

	cin >> m;
	for(int i = 1; i <= m; i++) {
		int num; cin >> num;
		q.push(mp(num, 0));
		check[num] = 0;
	}

	while(!q.empty()) {
		while(!q.empty()) {
			int curnode = q.front().first;
			int curcnt = q.front().second;
			q.pop();
			for(int i = 0; i < adj[curnode].size(); i++) {
				int nextnode = adj[curnode][i];
				if(check[nextnode] == -1) {
					qq.push(mp(nextnode, curcnt + 1));
					nearnode[nextnode].second++;
				}
			}
		}

		while(!qq.empty()) {
			int curnode = qq.front().first;
			int curcnt = qq.front().second;
			qq.pop();
			if(check[curnode] == -1 && nearnode[curnode].second * 2 >= nearnode[curnode].first) {
				check[curnode] = curcnt;
				q.push(mp(curnode, curcnt));
			}
		}
	}

	for(int i = 1; i < check.size(); i++) {
		cout << check[i] << " ";;
	}

	return 0;
}