인프런 커뮤니티 질문&답변

교재에서는 bfs로 구현했는데 저는 dfs로 구현해봤습니다.

그랬더니 시간초과가 발생했네요. 제가 작성한 코드가 올바른답이긴하지만 시간초과가 발생하는건지, 아니면 그냥 틀린건지 궁금합니다. 또한 올바른답 이맞다면 왜 시간초과가 발생하는지(시간복잡도 차이가 왜 크게 나는지)도 궁금합니다.

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int maxdepth=-1;

vector<vector<int>> a;

vector<bool> visited;

void dfs(int k, int depth);

int main() {

ios::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

int n,m;

cin >> n >> m;

a.resize(n + 1);

visited = vector<bool>(n + 1, false);

for (int i = 0; i < m; i++) {

int s,e;

cin >> s >> e;

a[e].push_back(s);

}

vector<int> result(n + 1, 0);

for (int i = 1; i <= n; i++) {

dfs(i, 0);

result[i] = maxdepth;

maxdepth = -1;

fill(visited.begin(), visited.end(), false);

}

int realmax = -1;

for (int i = 1; i <= n; i++) {

if (result[i] > realmax)realmax = result[i];

}

for (int i = 1; i <= n; i++) {

if (realmax==result[i])cout<<i<<' ';

}

}

void dfs(int k, int depth) {

if (maxdepth < depth)maxdepth = depth;

visited[k] = true;

for (int i : a[k]) {

if (!visited[i]) {

dfs(i, depth + 1);

}

}

visited[k] = false;

}