| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 1024 MB | 1177 | 486 | 377 | 43.634% |
문제
당신은 루머를 믿는가?
한 유명 심리학 실험에서는 사람들에게 두 개의 줄을 보여주고, 어떤 줄이 더 긴지 말하라 했다. 사실 한 사람을 제외하고 나머지는 실험자에 의해 사전에 조작된 사람들이었다. 조작된 사람들은 사실상 더 짧은 줄을 더 길다고 말했다. 주변 모두가 같은 답변을 하자, 진짜 피실험자 또한 짧은 줄이 더 길다고 말했다. 이 실험은 사람들이 주변인의 영향을 강하게 받는다는 것을 보여주었는데, 루머도 이와 같다.
루머는 최초 유포자로부터 시작한다. 최초 유포자는 여러 명일 수 있고, 최초 유포자를 제외하고 스스로 루머를 만들어 믿는 사람은 없다.
매분 루머를 믿는 사람은 모든 주변인에게 루머를 동시에 퍼트리며, 군중 속 사람은 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다.
루머를 믿는 순간부터 다른 말은 듣지 않기 때문에, 한번 믿은 루머는 계속 믿는다.
이때, 사람들이 루머를 처음 믿기 시작하는 시간을 알아내 보자.
입력
첫째 줄에 사람의 수 N이 주어진다. (1 <= N <= 200,000) 이는 1번 사람부터 N번 사람까지 있음을 의미한다.
둘째 줄부터 N개의 줄이 주어진다. 이 중 i(1 <= i <= N)번째 줄에는 i번 사람의 주변인들의 번호와 입력의 마지막을 나타내는 0이 공백으로 구분되어 주어진다. 번호는 1이상 N이하의 자연수이고, 같은 줄에 중복된 번호는 없다. 자기 자신이 주변인이거나 일방적으로 주변인인 경우는 없으며, 전체 양방향 주변인 관계는 1,000,000개를 넘지 않는다.
다음 줄에는 루머를 퍼뜨리는 최초 유포자의 수 M이 주어진다.(1 <= M <= N)
마지막 줄에는 최초 유포자의 번호가 공백으로 구분되어 주어진다. 최초 유포자의 번호는 중복되지 않는다.
출력
N개의 정수 t1, t2, ..., tN을 공백 단위로 출력한다. ti는 i번 사람이 루머를 처음 믿기 시작한 시간(분)이며, 충분히 많은 시간이 지나도 루머를 믿지 않을 경우 -1이다. 최초 유포자는 루머를 0분부터 믿기 시작했다고 생각한다.
접근
그래프를 이용한 문제이다. 시간과 메모리 제한이 넉넉했다.
1초부터 세면서 t - 1초에 루머를 믿은 사람과 연결된 edge를 살펴보면 된다.
하지만 매번 이웃의 수를 셀 수 없으니, 따로 테이블을 만들어서 관리했다.
풀이
cnt는 이웃 중 루머를 믿는 사람의 갯수이고 ans는 믿게된 시간을 저장하는 배열이다.
while loop를 돌면서 t - 1번째 시간에 루머를 믿은사람들인 v가 비어있으면 탈출한다.
매 loop에 v를 순회하면서 이웃들의 cnt를 증가시켜준다.
이 과정에서 절반 이상이 루머를 믿어 본인도 믿게 됐으면, tmp에 추가해준다.
v의 순회가 끝나면 v = tmp를 통해서 다시 초기화를 시켜준다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, M, cnt[200001], ans[200001], num;
vector<int> edge[200001], v, tmp;
int half(int idx)
{
return (edge[idx].size() + 1) / 2;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN(N);
FUP(i, 1, N)
{
while (1)
{
CIN(num);
if (!num) break;
edge[i].push_back(num);
}
cnt[i] = 0;
ans[i] = -1;
}
CIN(M);
while (M--)
{
CIN(num);
ans[num] = 0;
v.push_back(num);
}
int t = 1;
while (true)
{
if (v.empty()) break;
for (int node : v)
{
for (int next : edge[node])
{
if (ans[next] != -1) continue;
if (++cnt[next] >= half(next))
{
ans[next] = ans[node] + 1;
tmp.push_back(next);
}
}
}
v = tmp;
tmp.clear();
}
FUP(i, 1, N) COUT2(ans[i], "");
return 0;
}