글 읽기 - 인접리스트를 활용한 DFS로 풀었는데 시간초과가 나네요..

dhworhkd11 1년 전 0

인접리스트를 활용한 DFS로 풀었는데 N * O(N+e)의 시간 복잡도를 가질꺼라고 생각하고 있습니다.

N이 1만이라고 가정했을 때도 2초는 가능하다고 생각했는데 다른 방식으로 풀어야 할까요?

#include <stdio.h>
#include <vector>
using namespace std;
vector<unsigned char> adj[10001]; // 인접 노드 리스트
unsigned char tree[10001][10001] = {}; // 인접 행렬
bool visit[10001] = {};
int ans = 0;

void dfs(int s, int N, int sum) {
	if (ans <= sum) ans = sum;

	for (int i = 0; i < adj[s].size(); i++) {
		int next = adj[s][i];
		if (!visit[next]) {
			visit[next] = true;
			dfs(next, N, sum + tree[s][next]);
			visit[next] = false;
		}
	}
}

int main() {
	int N;
	scanf("%d",&N);
	for (int i = 0; i < N-1; i++) {
		int n1, n2, edge;
		scanf("%d %d %d", &n1, &n2, &edge);
		adj[n1].push_back(n2); 
		adj[n2].push_back(n1);
		tree[n1][n2] = tree[n2][n1] = edge;
	}
	
	for (int i = 1; i <= N; i++) {
		visit[i] = true;
		dfs(i, N, 0);
		visit[i] = false;
	}
	printf("%d", ans);
	return 0;
}

jpyo0803 1년 전 1

Dfs를 두번써서 O(N)에 푸는 방법이 있습니다!

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

문제

문제

출처

ICPC

인접리스트를 활용한 DFS로 풀었는데 시간초과가 나네요..

dhworhkd11 1년 전 0

jpyo0803 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말