[백준 19538] 루머

문제 : 19538 루머

유형 : BFS

아이디어 : 제한시간이 넉넉하기 때문에 어떻게 풀어도 풀리는 문제였다고 생각한다. 접근 방법은 큐 2개로 처음 큐에는 현재 노드들을 넣고 다른 큐에는 다음에 들어갈 수 있는 노드들을 넣었다. 현재노드에서 주변 노드들을 방문했는지 확인하고 방문된 노드가 연결된 간선의 개수의 절반이 넘으면 다음 노드들이 있는 큐에 넣어주었다. 현재 노드들을 담고 있는 큐가 비게되면 다른 큐에 있는 것들을 다시 넣어준다.

풀이 : 출발노드들을 방문 표시한 뒤 갈 수 있는 노드들을 큐에 넣어준다. 현재 위치에서 연결된 노드들의 방문 여부를 카운트하여 간선개수의 절반보다 많으면 Q에 푸시한다. 그리고 마지막에 visited 배열을 차례로 출력해준다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int n, m, visited[200001], c=  1;
vector<int> adj[200001];
queue<pair<int, int>> q;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		while (true) {
			cin >> x;
			if (x) adj[i].push_back(x);
			else break;
		}
	}
	memset(visited, -1, sizeof(visited));
	cin >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		visited[x] = 0;
		for (int i = 0; i < adj[x].size(); i++) q.push({ x, adj[x][i] });
	}
	while (!q.empty()) {
		queue<pair<int, int>> Q;
		vector<pair<int, int>> v;
		while (!q.empty()) {
			int now = q.front().second;
			int pre = q.front().first;
			q.pop();

			if (visited[now] != -1) continue;

			int cnt = 0;
			for (int i = 0; i < adj[now].size(); i++) {
				if (visited[adj[now][i]] != -1) cnt++;
			}
			if ((adj[now].size() + 1) / 2 <= cnt) {
				v.push_back({ now, visited[pre] + 1 });
				for (int i = 0; i < adj[now].size(); i++) {
					if (visited[adj[now][i]] == -1) Q.push({ now, adj[now][i] });
				}
			}
		}
		for (auto x : v) visited[x.first] = x.second;
		while (!Q.empty()) {
			q.push(Q.front()); Q.pop();
		}
	}

	for (int i = 1; i <= n; i++) cout << visited[i] << ' ';

	return 0;
}