글 읽기 - 2623번 시간초과나는데 도와주실 수 있나요?

dnflekals 4년 전 0

이번 문제 푸는데 시간초과 날 경우가 없을거 같은데 자꾸 시간초과가 뜨는데 왜 시간초과가 나는지 알려주실 수 있나요??

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
vector <int> g[1001];
queue <int> q;
int in[1001];
int check[1001];
int n, m;
int chk;

void dfs(int x) {
	if (check[x] == true) {
		chk++;
		return;
	}
	check[x] = true;
	for (int i = 0;i < g[x].size();i++) {
		int nx = g[x][i];
		dfs(nx);
	}
	check[x] = false;
}

bool checker() {
	for (int i = 1;i <= n;i++) {
		dfs(i);
		if (chk > 0) return 1;
	}
	return 0;
}

void bfs() {
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		printf("%d\n", x);

		for (int i = 0;i < g[x].size();i++) {
			int nx = g[x][i];
			in[nx]--;
			if (in[nx] == 0)q.push(nx);
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0;i < m;i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		for (int i = 0;i < x - 1;i++) {
			int z;
			scanf("%d", &z);
			g[y].push_back(z);
			in[z]++;
			y = z;
		}
	}
	for (int i = 1;i <= n;i++) {
		if (in[i] == 0) q.push(i);
	}
	if (checker()) printf("0\n");
	else bfs();

	return 0;
}

djm03178 4년 전 0

check를 true로 만들었다가 다시 false로 되돌리는 식으로 dfs를 하면 모든 경우의 수를 전부 탐색하게 되므로 지수 시간 복잡도가 되어 당연히 시간 초과가 됩니다.

dnflekals 4년 전 0

문제에서 노드의 수 n=1000이 최대이므로 1000*1000 해봤자 시간복잡도 안터지지 않나요?

djm03178 4년 전 1

지수 시간 복잡도가 된다고 말씀드렸습니다. 1000 * 1000이 아닙니다.

정점이 76개밖에 안 되는 아래 케이스가 왜 오래 걸리는지 생각해 보세요.

dnflekals 4년 전 0

아 정말 감사합니다. 저 예를 보니 왜 시간 복잡도가 1000*1000이 아닌지 알겠습니다.

정말 감사합니다!

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

문제

문제

출처

ICPC

2623번 시간초과나는데 도와주실 수 있나요?

dnflekals 4년 전 0

djm03178 4년 전 0

dnflekals 4년 전 0

djm03178 4년 전 1

dnflekals 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말