글 읽기 - BFS 는 시간초과나고 DFS 는 정상적으로 통과하는 이유가 있을까요

zungleif 3년 전 0

처음 문제를 봤을 때 간단하게 BFS 로 풀면 되겠다 했는데 자꾸 시간초과가 떠서... DFS 로 바꿔 푸니까 이건 또 잘 통과되네요

둘 다 시간복잡도는 O(MN) 이 아닌가요?

// 처음에 BFS 접근으로 풀었던 방법
#include <bits/stdc++.h>

//시간초과 wtf
using namespace std;
int N, M, A, B;
map<int, vector<int>> relation;
vector<pair<int, int>> hackable;
queue<int> q;
bool visited[10002];

int main()
{
  cin.tie(NULL);
  ios::sync_with_stdio(false);

  cin >> N >> M;
  // 해킹 관계를 mapped_type 이 vector 인 map 에 저장, B -> A
  // B 를 해킹하면 A 또한 해킹이 가능하다
  for (int i = 0; i < M; i++)
  {
    cin >> A >> B;
    relation[B].push_back(A);
  }

  int cnt = 0;

  // BFS, 1번 컴퓨터부터 N번 컴퓨터까지 해킹가능한 관계를 나타낸 그래프를
  // BFS 하고 총 개수를 cnt 에 저장한뒤 결과를 hackable 에 넣는다
  for (int i = 1; i <= N; i++)
  {
    q.push(i);
    visited[i] = true;
    while (!q.empty())
    {
      auto cur = q.front(); q.pop();
      ++cnt;
      for (auto pc : relation[cur])
      {
        if (visited[pc])  continue;
        else			  visited[pc] = true;
        q.push(pc);
      }
    }
    hackable.push_back({ cnt, i });
    memset(visited, false, sizeof(visited));
    cnt = 0;
  }

  // 최대값 중에서 중복된 케이스를 검사, 
  // 해당되는 번호들을 vector 인 order 에 넣는다
  // 먼저 hackable pair 은 first 값을 기준으로 내림차순으로 정렬
  sort(hackable.begin(), hackable.end(),
       [](pair<int, int> pa1, pair<int, int> pa2)
       { return pa1.first > pa2.first; });
  auto max_end = hackable.begin();
  auto max_val = hackable.begin()->first;
  while (++max_end != hackable.end() && max_val == max_end->first) {}
  vector<int> order;
  for_each(hackable.begin(), max_end,
           [&order](pair<int ,int> pa)
           { order.push_back((pa.second)); });

  // 오름차순으로 출력하기위한 sort
  sort(order.begin(), order.end());
  copy(order.begin(), order.end(), ostream_iterator<int>(cout," "));
  return 0;
}

// 마음을 다스리고 다시 DFS 로 풀어본 결과 잘만 통과된다
// 이건 대체 왜 돼
#include <bits/stdc++.h>
using namespace std;
int N, M, a, b;
// if A is hacked, it can lead to hacking hackable[A]
bool visited[10002];
int hackable[10002];
int cnt = 0;

bool DFS(vector<int>* g, int e)
{
  if(visited[e])
  {
	return false;
  }
  else
  {
    visited[e] = true;
    ++cnt;
  }
  for(auto i: g[e])
  {
    DFS(g, i);
  }
  return true;
}

int main()
{
  vector<int> graph[10002];
  cin.tie(NULL);
  ios::sync_with_stdio(false);

  cin >> N >> M;
  for(int i = 0; i < M; i++)
  {
    cin >> a >> b;
	graph[b].push_back(a);
  }
  for(int i = 1; i <= N; i++)
  {
    DFS(graph, i);
    hackable[i] = cnt;
    cnt = 0;
    memset(visited, false, sizeof(visited));
  }
  int max = 0;
  for(auto i: hackable)
  {
    if(max < i)
    {
      max = i;
    }
  }
  vector<int> max_group;
  for(int i = 1; i <=N; i++)
  {
    if(hackable[i] == max)
    {
      max_group.push_back(i);
    }  
  }
  sort(max_group.begin(), max_group.end());
  copy(max_group.begin(), max_group.end(), ostream_iterator<int>(cout, " "));
  return 0;
}

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

문제

문제

출처

ICPC

BFS 는 시간초과나고 DFS 는 정상적으로 통과하는 이유가 있을까요

zungleif 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말