글 읽기 - 1260번 DFS와 BFS 문제에서 메모리를 너무 잡아먹어요..

muscj7 6년 전 0

상황 : 맞았으나 메모리와 시간이 다른 사람들에 비해 높게 나옴.

간단하게 리뷰하겠습니다.

1) DFS- 1차원 배열 visit를 이용해 방문한 정점은 다시 방문(BFS호출)하지 않도록 하였습니다.

2) BFS- 1차원 배열 visit를 이용해 방문한 정점은 다시 방문(Queue에 삽입)하지 않도록 하였습니다.

의심가는 부분은 간선 배열(path[10001][10001])의 사이즈인데 모두 방문한 것이 아니라

입력 받은 N, M, V 값에 맞게만 루프를 돌렸는데도 이렇게 메모리가 높게 나오나요?

아니면 제가 놓친 부분이 있다면 알고싶습니다.

#include<iostream>
#include<queue>
using namespace std;

int N, M, V;
bool visit_dfs[1001], visit_bfs[1001], path[10001][10001]; // index : 1~
queue<int> Queue;

void dfs(int v) {
	printf("%d ", v);
	visit_dfs[v] = true;
	for (int i = 1; i <= N; i++)
		if (v != i && !visit_dfs[i] && path[v][i])
			dfs(i);
}
void bfs(int v) {
	Queue.push(v);
	visit_bfs[v] = true;

	while (!Queue.empty())
	{
		int dequeue = Queue.front();
		Queue.pop();
		printf("%d ", dequeue);

		for (int i = 1; i <= N; i++) {
			if (dequeue != i && !visit_bfs[i] && path[dequeue][i]) {
				Queue.push(i);
				visit_bfs[i] = true;
			}
		}
	}
}
int main()
{
	// 데이터 입력
	scanf("%d %d %d", &N, &M, &V);
	for (int m = 0; m < M; m++) {
		int a, b; // 경로(양방향) : a->b 또는 b->a
		scanf("%d %d", &a, &b);
		path[a][b] = path[b][a] = true;
	}

	// 문제 해결
	dfs(V);
	printf("\n");
	bfs(V);
	printf("\n");

	return 0;
}

djm03178 6년 전 1

변수는 선언한 시점에서 메모리가 할당됩니다.

그리고 path는 [정점][정점]으로 접근하기 때문에 10001씩 필요하지 않습니다. [1001][1001]이면 충분합니다.

muscj7 6년 전 0

djm03178님

아!! 그 부분을 제가 실수했네요. 2980kb 4ms로 나오네요. 감사합니다.

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

문제

문제

출처

ICPC

1260번 DFS와 BFS 문제에서 메모리를 너무 잡아먹어요..

muscj7 6년 전 0

djm03178 6년 전 1

muscj7 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말