글 읽기 - BFS로 풀이 질문드립니다.

hsw0194 3년 전 0

일단 N이 10000개 이하이니

신뢰관계는 인접리스트로 구현했습니0다

예를 들어 3이 1을 신뢰한다 ( 3-> 1)라고 하면

1을 신뢰하는 컴퓨터 인접리스트에 3을 추가합니다

이런방식으로 컴퓨터들을 돌면서 닿을수 있는 컴퓨터의 개수를 반환받은후

최대개수랑 비교한후 출력하는 코드인데요 자꾸 틀렷다고 하네여..

어디부분이 틀렷을까요?

#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

#define N_MAX 10001

int N, M, virus_max, virus_max_qt;

// int들을 모아놓은 벡터가 아니라 vector<int>들을 N_MAX개 모아놓은것
// vector<int> array임
vector<int> trust_ll[N_MAX];
vector<bool> visited(N_MAX, false);

void ans();

int bfs(queue<int>, vector<bool>);

int main(void) {
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    int src, dest;
    cin >> src >> dest;
    trust_ll[dest].push_back(src);
  }
  ans();
}

void ans() {
  vector<int> virus_max_set(N);
  virus_max = -1;
  virus_max_qt = 0;
  for (int i = 1; i <= N; i++) {
    // 1부터 N까지 i번 컴퓨터로 인해
    // 몇개의 컴퓨터가 감염이 되는지 시도
    queue<int> q;
    vector<bool> is_visited(N, false);

    q.push(i);
    is_visited[i] = true;

    // i번 컴퓨터로 인해서 총 몇대의 컴퓨터가 감염되는지
    int cnt = bfs(q, is_visited);

    if (virus_max < cnt) {
      virus_max = cnt;
      virus_max_qt = 0;
      virus_max_set[virus_max_qt++] = i;
    } else if (virus_max == cnt) {
      virus_max_set[virus_max_qt++] = i;
    }
  }
  for (int i = 0; i < virus_max_qt; i++) {
    cout << virus_max_set[i] << " ";
  }
}

int bfs(queue<int> q, vector<bool> is_visited) {
  int cnt = 1;
  while (!q.empty()) {
    int front = q.front();
    q.pop();

    for (int i = 0; i < trust_ll[front].size(); i++) {
      // i번재 컴퓨터가 front를 신뢰할수 있으면
      if(!is_visited[trust_ll[front][i]]){
        is_visited[trust_ll[front][i]]=true;
        q.push(trust_ll[front][i]);
        cnt++;
      }
    }
  }
  return cnt;
}

hsw0194 3년 전 0

찾았습니다 이부분이 문제였네요

허탈합니다 ㅠㅠ

vector is_visited(N, false);
// 를

vector is_visited(N+1,false);
// 로 해결하니 바로풀리네요..

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

문제

문제

출처

ICPC

BFS로 풀이 질문드립니다.

hsw0194 3년 전 0

hsw0194 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말