bfs로도 한번 풀어봤는데 메모리 초과가 뜹니다! 혹시 이유를 알 수 있을까요?

작성한 질문수 9

0

자세한 설명과 답변 감사합니다!!! 덕분에 막혔던 부분을 빠르게 해결할 수 있었습니다 ㅎㅎ 아 혹시 강의 내용 중 나온 선생님의 정답코드를 영상으로 말고 텍스트로 확인할 수 있는 방법이 있을까요??

0

안녕하세요 윤교님 ㅎㅎ

	while (q.size()) {
		int nextNode = q.front(); q.pop();
		for (auto i : computer[nextNode]) {
			if (visited[i] == 1)continue;
			q.push(i);

이 부분은 q.push를 할 때 visit가 안들어가져 있습니다. 즉, 방문한 정점은 다시 방문할 수도 있다는 것입니다.

BFS를 할 때 방문한 정점은 다시 방문하지 않도록 방문처리를 해주는 것이 중요합니다.

int dfs(int here) {  
	visited[here] = 1;
	int ret = 1; 
	for(int there : v[here]){
		if(visited[there]) continue;
		ret += dfs(there); 
	} 
	return ret;
}

이코드를 보시면 dfs가 재귀적으로 일어나면서

dfs -> visited처리 -> dfs -> visited처리

...

가 반복적으로 일어납니다.

이렇게 방문처리를 해주시는게 중요한데요.

이처리를 안해주면 방문한 정점도 다시한번 계속 방문 -> 무한루프

에 빠질 수가 있고 이를 통해 메모리초과가 발생할 수도 있습니다.

전역변수로 선생님과 같은 배열들의 크기를 잡았는데 제출시 메모리초과가 뜨는 이유는 bfs안에 queue를 만들어서 그런것일까요??

>> 보통은 전역변수로 하는게 좋고 그런 이유로 초과가 뜨기도 합니다. 다만 이코드는 그 부분 말고 다른 부분이 문제였던 것 같습니다.

추가로 시간복잡도는 주어진 문제의 변수에 범위를 보고 내가 쓸 로직과 비교하여 이 로직이 될지 안될지 판단이 어느정도 가능해 졌는데, 문제에서 제공한 제한된 공간복잡도를 만족하는지에 대한 판단은 어떻게 해야 될까요?
>> 보통은 배열 기준으로 1000만 미만은 된다고 보시면 됩니다. 다만 문제마다 다를 수 있으니 이것은 참고삼아 이렇구나 하고 진행하셔야 합니다.

어떤 문제는 1억짜리도 되기도 합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.