[C] 백준 - 7569번: 토마토 - 2

8월 11일(금) - 그래프와 순회 (7569번)

7569번: 토마토

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이전에 풀이했던 "7576번: 토마토" 문제의 풀이에서 약간만 더 추가하면 될 것으로 생각

 

- bfs 방식으로 풀이를 진행하며

- 입력으로 M,N,H와 그에 따른 토마토들의 상태가 주어진다

- bfs 함수에서는 배열을 활용한 큐를 이용해서, 3중 for문을 돌리면서 변수 days에다가 누적합을 진행한다

- 출력으로는 토마토가 익지 못하면 -1을, 익는다면 

[C] 백준 - 7576번: 토마토

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int M, N, H;

int box[101][101][101];
int visited[101][101][101];

int q[1000001][3];
int front = 0;
int rear = 0;

int dx[6] = { -1, 1, 0, 0, 0, 0 };
int dy[6] = { 0, 0, -1, 1, 0, 0 };
int dz[6] = { 0, 0, 0, 0, -1, 1 };

void bfs(void)
{
	while (front < rear)
	{
		int z = q[front][0];
		int y = q[front][1];
		int x = q[front][2];
		front++;
		
		for (int i = 0; i < 6; i++)
		{
			int next_x = x + dx[i];
			int next_y = y + dy[i];
			int next_z = z + dz[i];

			if (next_x < 1 || next_y < 1 || next_z < 1 || next_x > M || next_y > N || next_z > H)
			{
				continue;
			}
			if (box[next_z][next_y][next_x] == 0)
			{
				box[next_z][next_y][next_x] = 1;
				visited[next_z][next_y][next_x] = visited[z][y][x] + 1;
				q[rear][0] = next_z;
				q[rear][1] = next_y;
				q[rear][2] = next_x;
				rear++;
			}
		}
	}
}

int main(void)
{
	scanf("%d %d %d", &M, &N, &H);
	for (int k = 1; k <= H; k++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= M; i++)
			{
				box[k][j][i] = -1;
				visited[k][j][i] = 0;
			}
		}
	}

	for (int k = 1; k <= H; k++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= M; i++)
			{
				scanf("%d", &box[k][j][i]);

				if (box[k][j][i] == 1)
				{
					q[rear][0] = k;
					q[rear][1] = j;
					q[rear][2] = i;
					rear++;
				}
			}
		}
	}

	bfs();

	int days = 0;
	int count = 0;
	for (int k = 1; k <= H; k++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int i = 1; i <= M; i++)
			{
				if (days < visited[k][j][i])
				{
					days = visited[k][j][i];
				}
				if (box[k][j][i] == 0)
				{
					count = 1;
				}
			}
		}
	}

	if (count == 1)
	{
		printf("-1");
	}
	else
	{
		printf("%d", days);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ