글 읽기 - 이 코드랑 제 코드가 다른게 뭘까요..

kce0206 4년 전 0

https://jaimemin.tistory.com/950

7개월전 20번 가까이 제출해도 안되서

다시 도전해봤다가 미칠거같아서 정답코드 검색해봤어요ㅠ

저 코드랑 제 코드랑 다른게 뭔지 모르겠어요..

저는 시간초과만 떠요..

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int> r[100];
vector<int> l[100];
int cnt[100];
int rdfs(int now);
int ldfs(int now);
int main() {
	queue<int> q;
	int n, m,key;
	cin >> n>>m;
	key = (n + 1) / 2;
	int a, b;

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		r[b].push_back(a);
		l[a].push_back(b);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (rdfs(i) > key)
			ans++;
		else if (ldfs(i) > key)
			ans++;
	}

	cout << ans;
	return 0;
}
int rdfs(int now) {
	int res = 1;
	cnt[now] = 1;
	for (int i = 0; i < r[now].size(); i++) {
		if (cnt[r[now][i]] == 1)
			continue;
		cnt[r[now][i]] = 1;
		res += rdfs(r[now][i]);
		cnt[r[now][i]] = 0;
	}
	cnt[now] = 0;
	return res;
}
int ldfs(int now) {
	int res = 1;
	cnt[now] = 1;
	for (int i = 0; i < l[now].size(); i++) {
		if (cnt[l[now][i]] == 1)
			continue;
		cnt[l[now][i]] = 1;
		res += ldfs(l[now][i]);
		cnt[l[now][i]] = 0;
	}
	cnt[now] = 0;
	return res;
}

3587jjh 4년 전 1

cnt가 정점 방문 여부를 저장하는걸로 보이는데, dfs후에 방문 체크를 해제해버리면

완전탐색이 되어버려 시간초과가 납니다

kce0206 4년 전 0

아하 그렇네요!!!감사합니다!!

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

문제

문제

출처

ICPC

이 코드랑 제 코드가 다른게 뭘까요..

kce0206 4년 전 0

3587jjh 4년 전 1

kce0206 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말