글 읽기 - 14502 연구소 런타임에러

dbsthqkf 6년 전 0

안녕하세요

BFS알고리즘을 이용하여 14502 연구소 문제를 풀었는데 일주일째 해결을 못하고 있어 질문을 올렸습니다.

인터넷 서치해보니 백준 런타임 에러가 메모리 관련문제로 많이 발생하는것 같은데 도저히 못찼겠습니다..

buildWalls()는 3개의 벽을 쌓는 함수이고

spreadVirusWithBfs는 BFS 알고리즘으로 바이러스를 퍼뜨리는 함수입니다.

감사합니다.

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
int **map;
int **tmpMap;
int **virusMap;
int N=0,M=0;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int maxArea=0;

#define SIZE 1000
typedef struct Vertex{
	int dx;
	int dy;
}Vertex;

typedef struct Queue{
	int front;
	int rear;
	Vertex* item[SIZE];
}Queue;

void buildWalls(int cnt);
void spreadVirusWithBfs();
int numOfSafeArea(int** map);
int isEmpty(Queue* queue);

Queue* createQueue(){
	Queue* newQueue = (Queue*)malloc(sizeof(Queue));
	newQueue->front = -1;
	newQueue->rear = -1;
	return newQueue;
}

Vertex* createVertex(){
	Vertex* newVertex = (Vertex*)malloc(sizeof(Vertex));
	newVertex->dx = 0;
	newVertex->dy = 0;
}

void printQueue(Queue* queue){
	int i=0;
	if(queue->rear == -1)
		return;
	printf("============Print Queue ============\n");
	printf("front : %d, rear : %d\n", queue->front, queue->rear);
	for(i=queue->front; i<=queue->rear; i++){
		printf("[%d][%d]\n", queue->item[i]->dx, queue->item[i]->dy);
	}
	printf("====================================\n");
}

void enQueue(Queue* queue, Vertex* vertex){
	if(queue->front == -1){
		queue->front = 0;
	}
	queue->rear++;
	queue->item[queue->rear] = vertex;
}

Vertex* deQueue(Queue* queue){
	Vertex* vertex;
	vertex = createVertex();
	if(isEmpty(queue)){
		return vertex;
	}

	if(queue->front > queue->rear){
		queue->front = -1;
		queue->rear = -1;
	}else{
		vertex = queue->item[queue->front];
		queue->front++;
	}
	return vertex;
}

int isEmpty(Queue* queue){

	if(queue->rear == -1){
		return 1;
	}else{
		return 0;
	}
}

void copyArr(int** a, int** b){
	int i,j;
	for(i=0; i<N; i++){
		for(j=0; j<M; j++){
			a[i][j] = b[i][j];
		}
	}
}
int main(){
	int i, j, tmp;
    
	printf("N : ");
	scanf("%d", &N);
	
	printf("M: ");
	scanf("%d", &M);

	// memory allocate
	map = (int**)malloc(sizeof(int*)*N);
	tmpMap = (int**)malloc(sizeof(int*)*N);
	virusMap = (int**)malloc(sizeof(int*)*N);

	for(i=0; i<8; i++){
		map[i] = (int*)malloc(sizeof(int)*M);
		tmpMap[i] = (int*)malloc(sizeof(int)*M);
		virusMap[i] = (int*)malloc(sizeof(int)*M);
	}
	// input map data
	for(i=0; i<N; i++){
		for(j=0; j<M; j++){
			scanf("%d", &tmp);
			map[i][j] = tmp; 
		}
	}

	// build walls
	for(i=0; i<N; i++){
		for(j=0; j<M; j++){
			if(map[i][j] == 0){
				copyArr(tmpMap, map);
				tmpMap[i][j] = 1;
				buildWalls(1);
				tmpMap[i][j] = 0;
			}
		}
	}
	printf("maxArea : %d\n", maxArea);
	return 0;

}
void buildWalls(int cnt){
	int i, j;
	if(cnt == 3){
		copyArr(virusMap , tmpMap);
		spreadVirusWithBfs();
	}
	else{
		for(i=0; i<N; i++){
			for(j=0; j<M; j++){
				if(tmpMap[i][j] == 0){
					tmpMap[i][j] = 1;
					buildWalls(cnt+1);

					tmpMap[i][j] = 0;
				}
			}
		}
	}
}

void spreadVirusWithBfs(){
	int i,j;
	int dx[4] = {-1, 0, 1, 0};
	int dy[4] = {0, -1, 0, 1};
	int x, y;
	Queue* q;
	q = createQueue();

	for(i=0; i<N; i++){
		for(j=0; j<M; j++){
			if(virusMap[i][j] == 2){
				Vertex* v;
				v = createVertex();
				v->dx = i;
				v->dy = j;
				enQueue(q,v); 
			}
		}
	}

	while(!isEmpty(q)){
		Vertex* v = deQueue(q);
		for(i=0; i<4; i++){
			x = v->dx + dx[i];
			y = v->dy + dy[i];
			if(x >=0 && y >=0 && x < N && y < M){
				if(virusMap[x][y] == 0){
					virusMap[x][y] = 2;
					v->dx = x;
					v->dy = y;
					enQueue(q, v);
				}
			}

		}    
	}
    
	if(numOfSafeArea(virusMap) > maxArea){
		maxArea = numOfSafeArea(virusMap);
	}

}

int numOfSafeArea(int **map){
	int i, j;
	int cnt=0;
	for(i=0; i<N; i++){
		for(j=0; j<M; j++){
			if(map[i][j] == 0)
				cnt++;
		}
	}
	return cnt;
}

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

문제

문제

출처

ICPC

14502 연구소 런타임에러

dbsthqkf 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말