글 읽기 - (C++) DFS 시간초과 질문

ahdtld54 2년 전 0

DFS를 사용하여 코드를 작성했는데 시간초과가 발생합니다.

저는 DFS탐색 과정에서 MAX와 MIN을 갱신하는 방식을 생각했습니다. 그런데 다른 분들은 LCA방법을 사용하셨는데 이 문제에서는 특정 노드를 부모노드로 잡고 나머지 노드들의 depth를 구하기 위해서는 역시 DFS를 사용한 뒤에 LCA를 구해야한다고 생각해서 LCA방법으로 최대최소를 구하는 방법보다 처음부터 DFS를 통해 구하는 방법이 더 빠를것이라고 생각했습니다..

시간초과의 이유와 이 문제가 만약 LCA가 더 효율적이라면 그 이유가 궁금합니다ㅠㅜㅠㅜ

#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
#include <climits>
using namespace std;

int N, K;
vector<pair<int, int>> a[100001];
int DP[2][100001];
int c[100001];

void DFS(int end, int curr) {
	if (curr == end) {
		cout << DP[0][end] << ' ' << DP[1][end] << '\n';
		return;
	}

	for (int i = 0; i < a[curr].size(); i++) {
		int y = a[curr][i].first;
		if (!c[y]) {
			c[y] = true;
			DP[0][y] = min(min(DP[0][curr], DP[0][y]), a[curr][i].second);
			DP[1][y] = max(max(DP[1][curr], DP[1][y]), a[curr][i].second);
			DFS(end, y);
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		int q, w, r;
		cin >> q >> w >> r;
		a[q].push_back(make_pair(w, r));
		a[w].push_back(make_pair(q, r));
	}
	cin >> K;
	for (int i = 0; i < K; i++) {
		int start, end;
		for (int i = 1; i <= N; i++) {
			DP[0][i] = INT_MAX;
			DP[1][i] = INT_MIN;
		}
		memset(c, 0, sizeof(int)*(N + 1));
		cin >> start >> end;

		c[start] = true;
		DFS(end, start);
	}
	
}

djs100201 2년 전 0

dfs ->쿼리당 시간복잡도 O(N)
lca->쿼리당 시간복잡도 O(logN)

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

문제

문제

출처

ICPC

(C++) DFS 시간초과 질문

ahdtld54 2년 전 0

djs100201 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말