[백준 1325번] 효율적인 해킹 (C++)

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

평범한 BFS문제이다.

시간제한도 5초이므로 오래걸릴 각오도 해야한다.

주의할것은 문제를 잘 읽어야하는데 A가 B를 신뢰하면 B를 해킹했을 때 A까지 해킹되는 것이다. (A를 해킹했을 때 B가 해킹되는게 아님)

 

C++로 BFS연습하고 싶어서 한번 해봤는데, 벡터를 함수로 전달할 때 &연산자를 사용해야지 주소값이 넘어가면서 시간을 절약할 수 있다. 벡터 자체를 넘기면 시간이 굉장히 오래걸린다.전역변수로 선언해도 상관없지만,  그냥 함수로 전달해봤다.코드는 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define endl "\n"

using namespace std;
void BFS(int e, vector<vector<int>> &com, bool* visited,int* ans);
int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m, a, b;
  cin >> n >> m;
  bool* visited = new bool[n+1];
  memset(visited,false,sizeof(visited));
  int* ans = new int[n+1];
  vector<vector<int>> com(n+1,vector<int>());

  for(int i = 0; i < m; i++){
    cin >> a >> b;
    com[b].push_back(a);
  }

  for(int i = 1; i < n+1 ; i++){
    BFS(i, com, visited, ans);
    fill_n(visited, n+1, false);
  }

  int max_val = *max_element(ans+1, ans + n+1);
  for(int i = 1; i < n+1; i++){
    if(ans[i] == max_val) cout << i << ' ';
  }
}

void BFS(int e, vector<vector<int>> &com, bool* visited,int* ans){
  queue<int> q;
  int cnt = 1;
  q.push(e);
  visited[e] = true;
  while(!q.empty()){
    int tmp = q.front();
    q.pop();
    for(int i : com[tmp]) {
      if(!visited[i]){
        visited[i] = true;
        q.push(i);
        cnt++;
      }
    }
  }
  ans[e] = cnt;
}