글 읽기 - 이문제 DFS 탐색이 아닌가여..? 시간초과가....ㅠ 도와주세요

vhxpffltm12 6년 전 0

문제 예제는 잘 나오는데 시간초과가 나오네요..ㅠ 도와주세요

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<stack>
using namespace std;

int n, m, h[5001] = { 0 },visit[5001],ans=1,chk,ll=0;
int bb[5001] = { 0 },k=1;
vector<int> arr[5001];

void dfs(int a) {
	visit[a] = 1;
	//printf("%d %d\n", a,ans);
	for (int i = 0; i < arr[a].size(); i++) {
		
		if (visit[arr[a][i]] == 0 && h[a] < h[arr[a][i]]) {
			visit[arr[a][i]] = 1;
			ans++;
			dfs(arr[a][i]);
		}
		if (ans != 0) {
			ll = max(ans, ll);
		}
	}
	ans = 0;
	
}

int main()
{
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		dfs(i);
		printf("%d\n", ll);
		ll = 0;
		ans = 1;
		chk = 0;
		memset(visit, 0, n * sizeof(int));
		memset(bb, 0, n * sizeof(int));
	}
	return 0;
}

lyzqm 6년 전 1

N번 완전탐색으로는 시간초과가 날 수 밖에 없습니다.

이미 방문했던 정점에대해 메모이제이션하여 dp를 이용하면 푸실 수 있습니다.

jh05013 6년 전 1

완전탐색이 아니라 그냥 모든 정점을 방문하기만 하는 DFS를 쓰신 것 같은데, 그 방법으로 가장 긴 경로가 나온다는 보장은 전혀 없습니다.

chogahui05 6년 전 1

위상 정렬로 풀어보세요.

어떻게 푸는지는 안 알려드릴거에요.

vhxpffltm12 6년 전 0

조언들 감사합니다~ 다시 풀어볼께요.

chogahui05 6년 전 0

문제 추천을 원하신다면 제가 생각했을 때 단순한(?) 그래프여서

위상정렬만을 이용해서 사이클을 detect 할 수 있는 문제들을 추천해 드리겠습니다..

9521번 색칠 공부라던지..

9466번 텀 프로젝트라던지..

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

문제

문제

출처

ICPC

이문제 DFS 탐색이 아닌가여..? 시간초과가....ㅠ 도와주세요

vhxpffltm12 6년 전 0

lyzqm 6년 전 1

jh05013 6년 전 1

chogahui05 6년 전 1

vhxpffltm12 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말