๋ฌธ์ ๋ ์ฌ๊ธฐ์์ ํ์ธ
์ฝ๋๋ก ๋ฐ๋ก ๋ด๋ ค๊ฐ๋ ค๋ฉด ํด๋ฆญ
ํ์ด
๐๋ฌธ์ ์ ๋ชฉ : ํ ๋งํ
๐์นดํ
๊ณ ๋ฆฌ : ๊ทธ๋ํ ์ด๋ก
๐ํ์ด :
N ์ธ๋ก, M ๊ฐ๋ก, H ๋์ด, 1 ์ต์ํ ๋งํ , 0์ต์ง์์ํ ๋งํ , -1ํ ๋งํ ๊ฐ ์๋ ์นธ
ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ํ๋์ ์ต์ ํ ๋งํ ์ ์ธ์ ํ(์, ์๋, ์ผ, ์ค, ์, ๋ค) ์ต์ง ์์ ํ ๋งํ ๋ ์ต๊ฒ ๋๋ค. ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ ๋งํ ๋ค์ด ๋ฉฐ์น ์ด ์ง๋๋ฉด ๋ค ์ต๋์ง โ์ต์ ์ผ์โ
๋ด๊ฐ ๋ฐฐ์ด ๊ฒ
๋ ์ง ๊ตฌํ๊ธฐ
BFS๋ฅผ ๋๋ฆด ๋ MAP์ ์ซ์๋ฅผ ๋ฃ์ด์ ํ๋ฉด ๋์๋ค. -1, 0, 1๋ก๋ง ์ด๋ฃจ์ด์ง 3์ฐจ์ ๋ฐฐ์ด์ด์๊ณ 1์ด ํ ๋งํ ๊ฐ ์๋ ๊ฒ, 0์ด ์๋ ๊ฒ์ด์์ผ๋ 0์ผ ๊ฒฝ์ฐ์๋ โ์ํฅ์ ๋ฐ์ ํ ๋งํ โ+1๋ฅผ ํด๋น ์๋ฆฌ์ ํ ๋นํด์ฃผ๋ฉด ๋๋ค.
๊ฐ๋ น 1์ผ ์งธ์ ์ต๋ ํ ๋งํ ๋ค์, ์ต์ด์๋(=1) ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ผ๋ฏ๋ก 1์ ๋ํด 2๋ฅผ ์ ์ฅํ๊ณ ,
2์ผ ์งธ์ ์ต๋ ํ ๋งํ ๋ค์ ์ต์ด์๋(=2) ํ ๋งํ ์ 1์ ๋ํด 3์ ์ ์ฅํ๋ฉด ๋๋ค.
๊ทธ ํ ๋ฐฐ์ด์์ ๊ฐ์ฅ ํฐ ๊ฐ์ 1์ ๋นผ์ฃผ๋ฉด ๋๋ค.
์ค์ํ์ง ๋ง๊ธฐ
if (MAP[h][n][m] == 0) {
cout << -1; return 0;
}
์ฝ๋ ๋ด๋ถ main ๋งจ ๋ง์ง๋ง์ ๋ค์ด๊ฐ๋ ์์ if๋ฌธ์ โํ๋๋ผ๋ ์ต์ง ์์ ํ ๋งํ ๊ฐ ์๋ค๋ฉดโ -1๋ฅผ ์ถ๋ ฅํ๊ธฐ ์ํด ์กด์ฌํ๋ค. ๊ทธ๋ฌ๋ ์ฝ๋๋ฅผ ์ง๋ ๋์ค -1์ด ์๋ 0์ coutํด์ฃผ์ด์ ์ ์ ํค๋งธ์๋ค. ํํ TC์๋ ๊ฑธ๋ฆฌ์ง ์๋ ๋ถ๋ถ์ด์๋ค.
๊ผญ! ๋ฌธ์ ์์ ์ถ๋ก ๊ฐ๋ฅํ ๊ทน์ ์ด๊ณ ๊ฐ๋จํ ๋ชจ๋ ์์ ๋ฅผ ๋๋ ค๋ณด๋๋ก ํ์.
์ฝ๋
#include "pch.h"
/*
๋ฌธ์ ์ ๋ชฉ : ํ ๋งํ
์นดํ
๊ณ ๋ฆฌ : ๊ทธ๋ํ ์ด๋ก
ํ์ด :
N ์ธ๋ก, M ๊ฐ๋ก, H ๋์ด, 1 ์ต์ํ ๋งํ , 0์ต์ง์์ํ ๋งํ , -1ํ ๋งํ ๊ฐ ์๋์นธ
ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ํ๋์ ์ต์ ํ ๋งํ ์ ์ธ์ ํ(์, ์๋, ์ผ, ์ค, ์, ๋ค) ์ต์ง ์์
ํ ๋งํ ๋ ์ต๊ฒ ๋๋ค. ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ ๋งํ ๋ค์ด ๋ฉฐ์น ์ด ์ง๋๋ฉด ๋ค ์ต๋์ง '์ต์ ์ผ์'
*/
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 101;
int N, M, H;
int res;
int MAP[MAX][MAX][MAX]; // 10^6๊ฐ
queue < pair<int, pair<int, int>>> q;
bool isIn(int h, int n, int m)
{
return (h >= 0 && h < H) && (n >= 0 && n < N) && (m >= 0 && m < M);
}
int dir[6][3] = { {0,-1,0},{0,1,0},{0,0,1},{0,0,-1},{-1,0,0},{1,0,0} };
void BFS()
{
while (!q.empty())
{
int h = q.front().first;
int n = q.front().second.first;
int m = q.front().second.second;
q.pop();
for (int d = 0; d < 6; d++)
{
int dh = h + dir[d][0];
int dn = n + dir[d][1];
int dm = m + dir[d][2];
if (isIn(dh, dn, dm) && MAP[dh][dn][dm] == 0) {
MAP[dh][dn][dm] = MAP[h][n][m] + 1;
res = max(res, MAP[h][n][m]);
//cout << res << endl;
q.push(make_pair(dh, make_pair(dn, dm)));
}
}
}
return;
}
int main()
{
res = 0;
int tomato_n = 0;
cin >> M >> N >> H;
for(int h=0; h<H; h++)
for(int n=0;n<N;n++)
for (int m = 0; m < M; m++) {
cin >> MAP[h][n][m];
if (MAP[h][n][m] == 1) q.push(make_pair(h, make_pair(n, m)));
if (MAP[h][n][m] != -1) tomato_n++;
}
if ( (!q.empty()) && (q.size() == tomato_n))
{
cout << 0;
return 0;
}
if (q.empty())
{
cout << -1;
return 0;
}
BFS();
for (int h = 0; h < H; h++)
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++) {
if (MAP[h][n][m] == 0) {
cout << -1; return 0;
}
}
cout << res;
return 0;
}