https://www.acmicpc.net/problem/7569
전의 토마토 문제가 조금 변형된 문제이다.
3차원 배열을 한 번도 활용해 본 적이 없어 활용하여 풀어보았다.
단순히 전의 문제에서 3차원 요소만 더해주어 같이 검사하는 것이 아니라,
각각 검사하고 조건을 만들어주어야 했다.
재밌는 문제였다!
using System;
using System.IO;
using System.Text;
namespace B7569
{
class Program
{
static int M, N, H;
static int[,,] map = new int[101, 101, 101];
static bool[,,] visited = new bool[101, 101, 101];
static int[] dx = { -1, 1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
static int[] dh = { 0, 1, -1 };
static Queue<(int, int, int)> q = new Queue<(int, int, int)>();
static Queue<(int, int, int)> qNext = new Queue<(int, int, int)>();
static int day = -1;
static void BFS()
{
//q혹은 qNext
if (q.Count > 0)
{
while (q.Count > 0)
{
var deq = q.Dequeue();
int deqx = deq.Item1;
int deqy = deq.Item2;
int deqh = deq.Item3;
visited[deqx, deqy, deqh] = true;
//현재 위 아래
for (int h = 0; h < 3; h++)
{
deqh = deq.Item3 + dh[h];
if (deqh < 0 || deqh >= H)
continue;
visited[deqx, deqy, deqh] = true;
if (map[deqx, deqy, deqh] == -1 || map[deqx, deqy, deqh] == 1) continue;
if (map[deqx, deqy, deqh] == 0)
{
map[deqx, deqy, deqh] = 1;
qNext.Enqueue((deqx, deqy, deqh));
}
}
//deqh 초기화
deqh = deq.Item3;
for (int i = 0; i < 4; i++)
{
deqx = deq.Item1 + dx[i];
deqy = deq.Item2 + dy[i];
if (deqx < 0 || deqx >= N || deqy < 0 || deqy >= M)
continue;
visited[deqx, deqy, deqh] = true;
if (map[deqx, deqy, deqh] == -1 || map[deqx, deqy, deqh] == 1) continue;
if (map[deqx, deqy, deqh] == 0)
{
map[deqx, deqy, deqh] = 1;
qNext.Enqueue((deqx, deqy, deqh));
}
}
}
}
else
{
while (qNext.Count > 0)
{
var deq = qNext.Dequeue();
int deqx = deq.Item1;
int deqy = deq.Item2;
int deqh = deq.Item3;
visited[deqx, deqy, deqh] = true;
//현재 위 아래
for (int h = 0; h < 3; h++)
{
deqh = deq.Item3 + dh[h];
if (deqh < 0 || deqh >= H)
continue;
visited[deqx, deqy, deqh] = true;
if (map[deqx, deqy, deqh] == -1 || map[deqx, deqy, deqh] == 1) continue;
if (map[deqx, deqy, deqh] == 0)
{
map[deqx, deqy, deqh] = 1;
q.Enqueue((deqx, deqy, deqh));
}
}
//deqh 초기화
deqh = deq.Item3;
for (int i = 0; i < 4; i++)
{
deqx = deq.Item1 + dx[i];
deqy = deq.Item2 + dy[i];
if (deqx < 0 || deqx >= N || deqy < 0 || deqy >= M)
continue;
visited[deqx, deqy, deqh] = true;
if (map[deqx, deqy, deqh] == -1) continue;
else if (map[deqx, deqy, deqh] == 0)
{
map[deqx, deqy, deqh] = 1;
q.Enqueue((deqx, deqy, deqh));
}
}
}
}
}
static bool AllOK()
{
for (int h = 0; h < H; h++)
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
if (visited[x, y, h] == false && map[x, y, h] == 0)
return false;
}
}
}
return true;
}
static void Main()
{
StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
//입력
int[] mnh = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
M = mnh[0];
N = mnh[1];
H = mnh[2];
bool isOK = false;
for (int i = 0; i < H; i++)
{
for (int j = 0; j < N; j++)
{
int[] input = Array.ConvertAll(sr.ReadLine().Split(' '), int.Parse);
for (int k = 0; k < M; k++)
{
map[j, k, i] = input[k];
if (input[k] == 0) isOK = true;
}
}
}
if (!isOK) sw.Write(0); //0인 토마토가 없는 경우
else
{
for (int h = 0; h < H; h++)
{
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
//토마토가 익어있다면
if (map[x, y, h] == 1)
q.Enqueue((x, y, h));
}
}
}
while (q.Count > 0 || qNext.Count > 0)
{
day++;
BFS();
}
//모든 토마토가 익지 못하는 상황인가?
if (!AllOK()) sw.Write(-1);
else sw.Write(day);
}
sr.Close();
sw.Flush();
sw.Close();
}
}
}
q부분을 qNext로 그대로 가져와 틀렸다..이래서 코드는 복사하는 것이 아니라 다시 쓰는 것이라 하나 보다. 🥲🥲
슬슬 골드 문제 풀어가니 재밌지만 걸리는 시간도 늘어간다,,
'알고리즘 > 백준 BOJ' 카테고리의 다른 글
[ BOJ/C# ] 2667 단지번호붙이기 (0) | 2023.10.13 |
---|---|
[ BOJ/C# ] 2178 미로 탐색 (0) | 2023.10.12 |
[ BOJ/C# ] 7576 토마토 (0) | 2023.10.10 |
[ BOJ/C# ] 1012 유기농 배추 (0) | 2023.10.09 |
[ BOJ/C# ] 7568 덩치 (0) | 2023.10.09 |