글 읽기 - 메모리 초과 질문입니다.

pp10202 1년 전 0

현재 큐를 이용하여 BFS하는 방식으로 아기상어에서 가장 가까운 물고기를 찾아주고 있는데,

계속 메모리 초과가 나옵니다. visited 배열 설정을 q에 넣기 전에 해서, q 내부의 원소의 개수가 해봤자 얼마 안 될 거 같은데..

메모리 초과의 이유를 알려주시면 감사하겠습니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>

int n;
int map[20][20];
int dir[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
int fish_num[7] = {0, };
typedef struct shark_info {
	int x, y;
	int size, cnt;
} shark_info;

shark_info info;

typedef struct queue_node {
	int x, y, dist;
	struct queue_node* next;
} queue_node;

typedef struct queue {
	queue_node* top;
	queue_node* tail;
} queue;

queue* q;

int empty() {
	if (q->top == NULL) return 1;
	else return 0;
}

void add_queue(int x, int y, int dist) {

	queue_node* new_node = (queue_node*)malloc(sizeof(queue_node));
	new_node->x = x;
	new_node->y = y;
	new_node->dist = dist;
	new_node->next = NULL;

	if (q->top == NULL) {
		q->top = new_node;
		q->tail = new_node;
	}
	else {
		q->tail->next = new_node;
		q->tail = new_node;
	}
}

void delete_queue() {

	if (empty()) {
		printf("Queue is already empty\n");
		return;
	}

	queue_node* tmp = q->top;
	q->top = q->top->next;
}

queue_node* pop() {

	if (empty()) {
		//printf("Queue is already empty\n");
		return NULL;
	}
	queue_node* tmp = q->top;
	q->top = q->top->next;

	return tmp;
}

int serch(int x, int y) {
	// BFS using queue..
	int i, dist, cur_x, cur_y;
	int next_x, next_y, min_x, min_y;

	// 현재 위치를 큐에 넣고 시작
	add_queue(x, y, 0);
	queue_node* tmp = NULL;
	int visited[20][20] = {0, };
	visited[x][y] = 1;

	for (i = 1; i < info.size; i++) {
		if (fish_num[i] != 0) break;
	}
	if (i == info.size) return -1;

	while (1) {

		if (tmp != NULL)
			free(tmp);

		tmp = pop();
		// empty check	
		
		if (tmp == NULL) break;
		

		cur_x = tmp->x;
		cur_y = tmp->y;
		dist = tmp->dist;

		if (info.size > map[cur_x][cur_y] && map[cur_x][cur_y] != 0) {
			// 먹는 칸에 도달했다
			info.cnt += 1;
			map[x][y] = 0;
			min_x = cur_x, min_y = cur_y;
			while (!empty() && tmp->dist == dist) {

				if (info.size > map[tmp->x][tmp->y] && map[tmp->x][tmp->y] != 0) {
					if (tmp->x == min_x) {
						if (tmp->y < min_y) {
							min_y = tmp->y;
						}
					}
					if (tmp->x < min_x) {
						min_x = tmp->x;
						min_y = tmp->y;
					}
				}
				free(tmp);
				tmp = pop();
			}

			fish_num[map[min_x][min_y]]--;
			map[min_x][min_y] = 9;
			info.x = min_x;
			info.y = min_y;
			break;
		}

		for (i = 0; i < 4; i++) {
			// 범위 검사
			next_x = cur_x + dir[i][0];
			next_y = cur_y + dir[i][1];
			if (cur_x + dir[i][0] < 0 || cur_x + dir[i][0] >= n) continue;
			if (cur_y + dir[i][1] < 0 || cur_y + dir[i][1] >= n) continue;
			if (visited[next_x][next_y]) continue;
			if (info.size < map[next_x][next_y]) continue;

			visited[next_x][next_y] = 1;
			add_queue(next_x, next_y, dist + 1);
		}
	}
	
	if (tmp == NULL)
		return -1;
	else {
		if (info.cnt == info.size) {
			info.size++;
			info.cnt = 0;
		}
		return dist;
	}

}

void solve() {
	int sum = 0, tmp = 0;


	while (1) {
		tmp = serch(info.x, info.y);

		while (!empty()) {
			free(pop());
		}

		if (tmp == -1) break;
		else sum += tmp;
	}

	printf("%d", sum);
}

int main(void) {

	int i, j;

	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) {
				info.x = i;
				info.y = j;
				info.size = 2;
				info.cnt = 0;
			}
			else if (map[i][j] > 0) {
				fish_num[map[i][j]]++;
			}
		}
	}

	q = (queue*)malloc(sizeof(queue));
	q->top = NULL;
	q->tail = NULL;

	solve();

	return 0;
}

pp10202 1년 전 0

131번째 줄에 map[min_x][min_y]를 9가 아니라 0으로 만들어서 비워줘야 했는데..

다음 날 아침에 보니까 보이네요

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

문제

문제

출처

ICPC

메모리 초과 질문입니다.

pp10202 1년 전 0

pp10202 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말