BOJ 7569 : 토마토 (3차원)

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/7569

 

이후 설명 및 입/출력은 링크 참고

 

BOJ 7576 토마토는 2차원에서 토마토가 퍼져나갔다.

이번 문제는 3차원에서 토마토를 만들어가면 된다.

 

2차원에서는 4방향으로 토마토를 큐에 담았지만,

3차원에서는 좌표의 높이(h)에 대해 위, 아래 토마토를 추가해주면 된다.

즉, 총 6방향으로 BFS가 퍼져 나간다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS()
{
	for (int h = 1; h <= H; h++)
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= M; c++)
				/* 시작 토마토 담기 */

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			/* 2차원 토마토 */
		}

		/* 위 */
		if (MAP[out.h - 1][out.r][out.c] == 0)
		{
			queue[wp].h = out.h - 1;
			queue[wp].r = out.r;
			queue[wp++].c = out.c;

			MAP[out.h - 1][out.r][out.c] = MAP[out.h][out.r][out.c] + 1;
		}

		/* 아래 */
		if (MAP[out.h + 1][out.r][out.c] == 0)
		{
			queue[wp].h = out.h + 1;
			queue[wp].r = out.r;
			queue[wp++].c = out.c;
			
			MAP[out.h + 1][out.r][out.c] = MAP[out.h][out.r][out.c] + 1;
		}
	}
}

 

그리고 input, findAns등도 3차원 버전으로 만들어주면 된다. 최종 코드를 참고하자.

#include <stdio.h>

#define MAX (100 + 20)

int M, N, H;
int MAP[MAX][MAX][MAX];

typedef struct st
{
	int h;
	int r;
	int c;
} QUEUE;

QUEUE queue[MAX*MAX*MAX];
int wp, rp;


void input()
{
	scanf("%d %d %d", &M, &N, &H);

	for (int h = 0; h <= H + 1; h++)
		for (int r = 0; r <= N + 1; r++)
			for (int c = 0; c <= M + 1; c++)		
				MAP[h][r][c] = -1;

	for (int h = 1; h <= H; h++)
		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= M; c++)
				scanf("%d", &MAP[h][r][c]);
}

void output()
{
	for (int h = 0; h <= H + 1; h++)
	{
		for (int r = 0; r <= N + 1; r++)
		{
			for (int c = 0; c <= M + 1; c++)
				printf("%d ", MAP[h][r][c]);
			putchar('\n');
		}
		putchar('\n');
	}
}


/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS()
{
	for (int h = 1; h <= H; h++)
	{
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= M; c++)
			{
				if (MAP[h][r][c] == 1)
				{
					queue[wp].h = h;
					queue[wp].r = r;
					queue[wp++].c = c;
				}
			}
		}
	}

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr, nc;
			
			nr = out.r + dr[i];
			nc = out.c + dc[i];

			if (MAP[out.h][nr][nc] == 0)
			{
				queue[wp].h = out.h;
				queue[wp].r = nr;
				queue[wp++].c = nc;
				
				MAP[out.h][nr][nc] = MAP[out.h][out.r][out.c] + 1;
			}
		}

		/* 위 */
		if (MAP[out.h - 1][out.r][out.c] == 0)
		{
			queue[wp].h = out.h - 1;
			queue[wp].r = out.r;
			queue[wp++].c = out.c;

			MAP[out.h - 1][out.r][out.c] = MAP[out.h][out.r][out.c] + 1;
		}

		/* 아래 */
		if (MAP[out.h + 1][out.r][out.c] == 0)
		{
			queue[wp].h = out.h + 1;
			queue[wp].r = out.r;
			queue[wp++].c = out.c;
			
			MAP[out.h + 1][out.r][out.c] = MAP[out.h][out.r][out.c] + 1;
		}
	}
}

int findAns()
{
	int max = 0;
	for (int h = 1; h <= H; h++)
	{
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= M; c++)
			{
				if (MAP[h][r][c] == 0) return -1;
				if (MAP[h][r][c] > max) max = MAP[h][r][c];
			}
		}
	}

	return max - 1;
}

int main(void)
{
	input();

	BFS();

	printf("%d\n", findAns());

	return 0;
}