김로그

7576번 토마토

7576번 토마토

bfs문제인 토마토 동적할당으로 풀었으면 메모리 사용을 좀 더 줄일 수 있었을것 같다.

//https://www.acmicpc.net/problem/7576
//2016.04.15

#include <stdio.h>
#define test 0
void show();

int M, N;//x ,y
int time = 1;
int tomato = 0;

int map[1001][1001] = {0,};
int q[1002001][2];
int front=0, rear=0;
const int di[] = { -1, 1, 0, 0 };
const int dj[] = { 0, 0, 1, -1 };

int main(){
#if test
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d %d",&M,&N);
	for (int y = 0 ; y < N ; y++){
		for(int x = 0 ; x < M ; x++){
			scanf("%d",&map[y][x]);
			if(map[y][x] == 0 || map[y][x] == 1){
				tomato ++;
				if(map[y][x] == 1){
					q[front][0]  = x;
					q[front++][1] = y;
				}
			}
		}
	}

	while(!(front == rear)){
		int tempx = q[rear][0];
		int tempy = q[rear++][1];
		tomato--;
		for(int i = 0 ; i < 4 ; i++){
			int x = tempx + di[i];
			int y = tempy + dj[i];

			if( x < 0 || x > M -1|| y < 0 || y > N -1)continue;
			if(map[y][x] == 0){
				map[y][x] = map[tempy][tempx] +1;
				if(time < map[y][x])time = map[y][x];
				q[front][0]  = x;
				q[front++][1] = y;
			}
		}
#if test
		show();
#endif
	}
	if(tomato == 0)
		printf("%d\n",time-1);
	else
		printf("%d\n",-1);
	return 0;
}

void show(){
	printf("------- %d  %d---------\n",time,tomato);
	for(int i  =0 ; i < N ; i++)
	{
		for(int j = 0 ; j < M ; j++)
			printf("%d ",map[i][j]);

		printf("\n");
	}
}

3차원 토마토

7569번 토마토

같은 방법으로 푼다. 주의 할 점은 선형 queue를 사용할 경우 사이즈가 너무 커진다는 점을 유의 해야한다.

#include <stdio.h>
#define size 101*101*101

int q[size][3] = { 0, };

int main() {
	int M, N, H;
	int map[101][101][101] = { 0, };
	int tomato = 0;

	const int nx[6] = { 1, -1, 0 , 0, 0, 0 };
	const int ny[6] = { 0, 0, 1 , -1, 0, 0 };
	const int nz[6] = { 0, 0, 0 , 0, 1, -1 };
	int front = 0, rear = 0;

	int time = 0;

	scanf("%d %d %d", &M, &N, &H);
	for (int z = 0; z < H; z++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				scanf("%d", &map[z][y][x]);
				if (map[z][y][x] == 0 || map[z][y][x] == 1) {
					tomato++;
					if (map[z][y][x] == 1) {
						q[front][0] = x;
						q[front][1] = y;
						q[front++][2] = z;
					}
				}
			}
		}
	}

	while (!(front == rear)) {
		int tempX = q[rear][0];
		int tempY = q[rear][1];
		int tempZ = q[rear++][2];
		tomato--;
		for (int i = 0; i < 6; i++) {
			int x = tempX + nx[i];
			int y = tempY + ny[i];
			int z = tempZ + nz[i];

			if (x< 0 || y < 0 || z < 0 || x > M - 1 || y > N - 1 || z > H - 1)continue;

			if (map[z][y][x] == 0) {
				map[z][y][x] = map[tempZ][tempY][tempX] + 1;

				q[front][0] = x;
				q[front][1] = y;
				q[front++][2] = z;

				if (time < map[z][y][x]) time = map[z][y][x];
			}
		}
	}
	if (tomato == 0) {
		printf("%d\n", time - 1);
	}
	else
		printf("%d\n", -1);
	return 0;
}