글 읽기 - [c++] 19538번 bfs 문제 질문입니다.

gi5005 3년 전 0

bfs로 각 노드 탐색하면서 다음 노드의 근처사람이 평균보다 많이 루머를 믿고있으면 queue에 push해주면서 탐색했는데 틀렸다고 나옵니다. 일단 문제에서 주어진 예제 2개는 잘 돌아가는데 뭐가 문제인지 모르겠습니다.

반례찾아주시면 감사하겠습니다..ㅠㅠ

#include <bits/stdc++.h>
using namespace std;
#define MAX 200010
#define INF 999999999

int N;              //사람수
int M;              // 유포자 수
vector<int> V[MAX]; // 관계
vector<int> D;      //처음 유포자
int bl[MAX];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(bl, -1, sizeof(bl)); // 믿는지 여부
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        while (1)
        {
            int fred;
            cin >> fred;
            if (fred == 0)
            {
                break;
            }
            V[i].push_back(fred);
        }
    }
    cin >> M;
    for (int i = 0; i < M; i++)
    {
        int diff;
        cin >> diff;
        D.push_back(diff);
        bl[diff] = 0;
    }
    queue<pair<int, int>> q; // nextnode, time
    for (int i = 0; i < D.size(); i++)
    {
        q.push({D[i], 0});
    }
    while (!q.empty())
    {
        int curNode = q.front().first;
        int curTime = q.front().second;
        if (bl[curNode] != -1)
        {
            bl[curNode] = min(curTime, bl[curNode]);
        }
        else
        {
            bl[curNode] = curTime;
        }
        q.pop();
        for (int i = 0; i < V[curNode].size(); i++)
        {
            int nextNode = V[curNode][i];
            if (bl[nextNode] >= 0)
                continue;
            int isRumer = 0;
            for (int i = 0; i < V[nextNode].size(); i++)
            {
                if (bl[V[nextNode][i]] >= 0)
                    isRumer++;
            }
            if(!(isRumer||V[nextNode].size())) 
                continue;
                
            if (V[nextNode].size() / isRumer <= 2)
            {
                q.push({nextNode, curTime + 1});
            }
        }
    }
    for (int i = 1; i <= N; i++)
    {
        cout << bl[i] << " ";
    }
}

shg9411 3년 전 1

이 부분 V[nextNode].size()가 3이고 isRumer가 2이라면 어떻게 될까요.

if (V[nextNode].size() / isRumer <= 2){
    q.push({nextNode, curTime + 1});
}

gi5005 3년 전 1

근처 3명중에 2명이 믿고있는거니까 들어가야하는게 맞는거 아닌가요....?

shg9411 3년 전 1

예시를 잘못 들었었네요.

5, 2입니다.

gi5005 3년 전 0

아하.........그렇군요 감사합니다...!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] 19538번 bfs 문제 질문입니다.

gi5005 3년 전 0

shg9411 3년 전 1

gi5005 3년 전 1

shg9411 3년 전 1

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말