글 읽기 - 시간초과가 뜨는데 해결책좀 알려주세요

yoseong92 7년 전 0

큐를 이용해서 만들었고 익은 토마토가 아닐경우 일때만

검사하는데 왜 시간초과가 나오는지 모르겠네요..

#include <stdio.h>
#define MAXSIZE 30000
#define SIZE 1001 

int queue[MAXSIZE];
int front, rear;
int tomato[SIZE][SIZE] = {0,};

void init_queue();
void clear_queue();
int isempty();
int push(int val);
int pop();

int main(void){

	int n=0, m=0;
	int tmp[SIZE] = {0,};
	int x, y;

	scanf("%d%d", &n, &m);

	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++)
			scanf("%d", &tomato[i][j]);
	}

	int k = 0;
	for(int i = 0; i < m; i++){
		for(int j = 0; j < n; j++){
			if(tomato[i][j] == 1){
				tmp[k] = j;
				tmp[k+1] = i;
				k += 2;
			}
		}
	}

	

	for(int i = 0; i < k; i++){
		push(tmp[i]);	
	}


	int day[SIZE][SIZE] = {0, };

	while(isempty()==0){
		x = pop();
		y = pop();



		if((x-1) >= 0 && (x-1) < n && y >= 0 && y < m){
			if(tomato[0][0] == 1 && tomato[n-1][m-1] == 1){
				break;
			}
			if(tomato[x-1][y] == 0){
				push(x-1);
				push(y);
				tomato[x-1][y] = 1;
				day[x-1][y] = day[x][y] + 1;
			}
			if(tomato[x+1][y] == 0){
				push(x+1);
				push(y);
				tomato[x+1][y] = 1;
				day[x+1][y] = day[x][y] + 1;
			}
			if(tomato[x][y-1] == 0){
				push(x);
				push(y-1);
				tomato[x][y-1] = 1;
				day[x][y-1] = day[x][y] + 1;
			}
			if(tomato[x][y+1] == 0){
				push(x);
				push(y+1);
				tomato[x][y+1] = 1;
				day[x][y+1] = day[x][y] + 1;
			}
		}
	}

	if(day[0][0] > day[n-1][m-1]){
		printf("%d\n", day[0][0]);
	}
	else{
		printf("%d\n", day[n-1][m-1]);
	}


}

void init_queue(void){
	front = rear = 0;
}

void clear_queue(void){
	front = rear;
}

int isempty(void){
	if(front == rear){
		return 1;
	}
	return 0;
}

int push(int val){
	if((rear+1) % MAXSIZE == front){ 
		return (-1); 
	}
	queue[rear] = val;
	rear = ++rear % MAXSIZE;
	return val;
}

int pop(void){
	int i;
	if(front == rear){ 
		return (-1); 
	}
	i = queue[front];
	front = ++front % MAXSIZE;
	return i;
}

skynet 7년 전 0

코드에 주석을 달아 주세요!

Queue로 접근하는 BFS 탐색을 구현 하신거 같은데

코드를 상세히 보지는 못했지만, 이미 죽은 토마토를 또 죽이는거 같습니다.

1. 처음 Push 조건

-> 처음에 익은 토마토를 많이 줄수 있습니다.(익은 토마토를 모두 push해주어야 합니다.)

tmp변수를 사용하시는데 어떤 목적인지 모르겠습니다. (방문 했는지 검사하는 목적?, DP사용?)

2. Pop() algorithm

-> Pop() 을 해주면서 주변 토마토를 전염(?) 시킬때 전염되는 토마토의 '죽은 날짜'를 push 해주시면 됩니다.

여기서 조건이 이미 익은 토마토는 제외 하여아 합니다. 전염 방향은 위에서 구현 하신데로 4방입니다.

3. 날짜 카운트

Queue의 변수가 day가 됩니다.

맨처음에 0을 push, pop 하고 pop이 push를 콜하면 1씩 늘어 나게 설계를 하면

맨마지막에 pop되는 queue의 값이 day가 됩니다.

4. 3차원 문제의 경우 메모리 제한에 걸릴수 있음으로 변수를 적절히 조절하면 아리가또 할거 같습니다.

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