백준 7576 토마토

그냥 눈대중으로 풀었다.

첫번째로 푼것 :

    
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct {
	int position;
	int time;
}tomato;


int M, N;
int Map[1000][1000];
queue q;
int min_count;
int dirx[4] = { 0,0,1,-1 };
int diry[4] = { -1,1,0,0 };
clock_t start, endi;

void Input() {
	
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &Map[i][j]);
			if (Map[i][j] == 1) {
				q.push({ i*M + j,0 });
			}
		}
	}
	
	start = clock();
}

int Calc() {
	while (!q.empty()) {
		int position = q.front().position;
		int count = q.front().time;
		q.pop();
		int depth = position / M;
		int width = position % M;

		if (min_count < count) {
			min_count = count;
		}
		 
		for (int i = 0; i < 4; i++) {
			int next_x = width+dirx[i];
			int next_y = depth+diry[i];
			
			if (next_x<0 || next_x>=M || next_y<0 || next_y>=N || Map[next_y][next_x] != 0) continue;
			Map[next_y][next_x] = 1;
			q.push({ next_y*M + next_x ,count+1});
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 0) return -1;
		}
	}
	endi = clock();
	printf("%.2f",(double)(endi - start) / CLOCKS_PER_SEC );
	return min_count;
}

void Solve() {
	Input();
	printf("%d", Calc());
}


int main(void) {
	Solve();
	return 0;
}

 

2. 두번째 :

i*M+j하는 연산을 세이브하고 따로 메모리 저장소를 만들어 사용해보았다. 그러나 메모리만 쓰고 시간은 같은 걸 봐선 큐에서 뭔가 값을 가져오는 연산 자체가 느리다는걸 알수 있다.

 

    
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef struct {
	int position_x;
	int position_y;
	int time;
}tomato;


int M, N;
int Map[1000][1000];
queue q;
int min_count;
int dirx[4] = { 0,0,1,-1 };
int diry[4] = { -1,1,0,0 };
//clock_t start, endi;

void Input() {
	
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &Map[i][j]);
			if (Map[i][j] == 1) {
				q.push({j,i,0 });
			}
		}
	}
	
	/*start = clock();*/
}

int Calc() {
	while (!q.empty()) {
		int positionx = q.front().position_x;
		int positiony= q.front().position_y;
		int count = q.front().time;
		q.pop();

		if (min_count < count) {
			min_count = count;
		}
		 
		for (int i = 0; i < 4; i++) {
			int next_x = positionx+dirx[i];
			int next_y = positiony+diry[i];
			
			if (next_x<0 || next_x>=M || next_y<0 || next_y>=N || Map[next_y][next_x] != 0) continue;
			Map[next_y][next_x] = 1;
			q.push({ next_x,next_y ,count+1});
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 0) return -1;
		}
	}
	/*endi = clock();*/
	/*printf("%.2f",(double)(endi - start) / CLOCKS_PER_SEC );*/
	return min_count;
}

void Solve() {
	Input();
	printf("%d", Calc());
}


int main(void) {
	Solve();
	return 0;
}