백준 19538 - 루머(C++)

문제 링크입니다. https://www.acmicpc.net/problem/19538

19538번: 루머

BFS로 풀 수 있는 문제입니다.

1~N번 사람과 연결된 사람들이 주어지고, 루머를 퍼트립니다.

이때 X번 사람이 몇분만에 루머를 믿는지를 구하는 문제입니다.

 

X번 사람이 루머를 믿는 조건은 자신과 연결된 사람 중, 과반수 이상이 믿으면 X번 사람도 믿게 됩니다.

 

그렇다면 배열 하나를 만들어, X번을 탐색하려고 할 때마다 해당 배열의 값을 늘려준뒤, 조건에 만족할 때, 탐색에 넣어주면 됩니다.

 

자신과 연결된 사람은 바로 알 수 있습니다.

vector인 connect에 자신과 연결된 사람이 저장되어 있기 때문입니다.

 

하지만, vector안에는 중복되어 있는 값들이 존재합니다.

문제 예시를 들어보면, 1번 connect vector에는  (2, 2, 3, 3)이 저장되어 있을 것입니다.

따라서 중복된 값을 없애줘야합니다.

for(int i = 1; i <= N; i++){
    sort(connect[i].begin(), connect[i].end());
    connect[i].erase(unique(connect[i].begin(), connect[i].end()), connect[i].end());
}

해당 코드가 중복된 값을 지우는 코드입니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <cmath>
#define P pair<int, int>
#define PP pair<int, P>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M;
vector<int> start;
vector<int> connect[200001];
int check[200001];
int believe[200001];

void bfs(){
    memset(check, -1, sizeof(check));
    queue<P> q;
    for(int i = 0; i < start.size(); i++){
        q.push({start[i], 0});
        check[start[i]] = 0;
    }
    while(!q.empty()){
        int x = q.front().F;
        int cnt = q.front().S;
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] != -1) continue;
            believe[xx]++;
            int can_go = 0;
            if(connect[xx].size() % 2 == 0) can_go = connect[xx].size() / 2;
            else if(connect[xx].size() % 2 == 1) can_go = connect[xx].size() / 2 + 1;
            if(believe[xx] >= can_go){
                believe[xx]++;
                check[xx] = cnt + 1;
                q.push({xx, cnt+1});
            }
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        sort(connect[i].begin(), connect[i].end());
        connect[i].erase(unique(connect[i].begin(), connect[i].end()), connect[i].end());
    }
    bfs();
    for(int i = 1; i <= N; i++) cout << check[i] << " ";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++){
        while(1){
            int x;
            cin >> x;
            if(x == 0) break;
            connect[i].push_back(x);
            connect[x].push_back(i);
        }
    }
    cin >> M;
    for(int i = 1; i <= M; i++){
        int x;
        cin >> x;
        start.push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요