글 읽기 - 민식우선탐색 DFS로 풀었는데 메모리초과가 납니다..

skdltm357 5년 전 0

DFS로 풀었는데 메모리초과가 나와서 도무지 어디서 틀린지 모르겠습니다...

#include <iostream>
using namespace std;
bool **grid;
bool *visit;
int N,M;
void dfs(int n){
	cout<<n<<" ";
	visit[n]=true;
	int cnt=0;
	for(int i=1;i<=N;++i){
		if(grid[n][i]&&visit[i]==false)++cnt;
	}
	
	if(cnt==0)return;
	int select=0;
	if((cnt)%2==1){
		for(int i=1;i<=N;++i)
			if(grid[n][i]&&visit[i]==false){
				if(select==cnt/2){
					dfs(i);
					return;
				}else ++select;
			}
	}else{
		for(int i=1;i<=N;++i){
			if(grid[n][i]&&visit[i]==false){
				dfs(i);
			}
		}
	}
}
int main(){
	N,M;
	cin>>N>>M;
	
	visit = new bool[N+1];
	grid = new bool*[N+1];
	
	for(int i= 0;i<=N;++i) grid[i] = new bool[N+1];
	for(int i=0;i<=N;++i){
		visit[i]=false;
		for(int j=0;j<=N;++j){
			grid[i][j] = false;
		}
	}
	for(int i=0;i<M;++i){
		int x,y;
		cin>>x>>y;
		grid[x][y]=true;
		grid[y][x]=true;
	}
	dfs(1);
	for( int i=0;i<=N;++i){
		delete [] grid[i];
	}
	delete[] grid;
	delete[] visit;
	return 0;
}

jh05013 5년 전 1

입력 범위를 본 다음, 사용하는 메모리가 최대 얼마인지 계산해 보세요.

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

문제

문제

출처

ICPC

민식우선탐색 DFS로 풀었는데 메모리초과가 납니다..

skdltm357 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말