글 읽기 - 간단한질문! visited 벡터 초기화 방법

seecimi 5년 전 0

안녕하세요.

문제를 풀다가 궁금한점이 있어서 이렇게 글을 쓰게 되었습니다!

저는 visited를 초기화할때, dfs방향 그대로 초기화해서

visited[here] = false;

위의 연산 횟수를 최소화 하려 했습니다. 그런데 시간초과가 나왔습니다.

이렇게 초기화 했더니, 시간초과가 나오지 않았습니다.

visited = vector<bool> (N+1, false);

dfs_reset 함수와, visited = vector<bool> (N+1, false)

왜이리 시간차이가 많이나는건가요?

// 사용하면 시간초과
void dfs_reset(int here)
{
	visited[here] = false;
	for(int i = 0; i < graph[here].size(); i++)
		if(visited[graph[here][i]])
			dfs_reset(graph[here][i]);
}

// 시간초과 x
visited = vector<bool> (N+1, false);

ploffer11 5년 전 1

재귀 호출은 대부분의 경우에서 느립니다.

seecimi 5년 전 0

함수는 활성 레코드(Activation Record)에 관련 정보를 저장하는데, 이 활성 레코드들이 스택 메모리에 순서대로 저장된 뒤 차례로 Pop되어 처리된다. 이 과정에서 문맥 변경(Context Switch)이 일어나기 때문에 재귀 호출은 반복 호출에 비해 수행 시간이 더 느려질 수 밖에 없다

출처: https://itance.tistory.com/entry/재귀의-문제점 [ITance]

감사합니다.

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

문제

문제

출처

ICPC

간단한질문! visited 벡터 초기화 방법

seecimi 5년 전 0

ploffer11 5년 전 1

seecimi 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말