๋ฌธ์ ๋ ์ฌ๊ธฐ์์ ํ์ธ
์ฝ๋๋ก ๋ฐ๋ก ๋์ด๊ฐ๊ธฐ
๋ฌธ์ ํ์ด
๐์นดํ
๊ณ ๋ฆฌ : ๊ทธ๋ํ?
๐๋ฌธ์ ๋ช
: ์ฐ๊ตฌ์
๐ํ์ด :
์ฐ๊ตฌ์๋ ํฌ๊ธฐ๊ฐ N*M์ธ ์ง์ฌ๊ฐํ, ๋ฒฝ์ ์นธ ํ๋๋ฅผ ๊ฐ๋ ์ฐจ์งํ๋ค.
๋ฐ์ด๋ฌ์ค๋ ์ํ์ข์ฐ ์ธ์ ํ ๋น ์นธ์ผ๋ก ํผ์ ธ๋๊ฐ๋ค. ์๋ก ์ธ์ธ ์ ์๋ ๋ฒฝ์ ๊ฐ์๋ 3๊ฐ์ด๋ฉฐ, ๊ผญ 3๊ฐ๋ฅผ ์ธ์์ผ ํ๋ค.
0์ ๋น์นธ, 1์ ๋ฒฝ, 2๋ ๋ฐ์ด๋ฌ์ค์ด๋ค.
๋ฒฝ์ 3๊ฐ ์ธ์ด ๋ค, ๋ฐ์ด๋ฌ์ค๊ฐ ํผ์ง ์ ์๋ ๊ณณ์ ์์ ์์ญ์ด๋ผ๊ณ ํ๋ค.
1. ๋ฒฝ ์์ฑ์ ๋ชจ๋ ๊ฒฝ์ฐ์ ์ ๋ง๋ค๊ธฐ
2. BFS๋ก ๋ฐ์ด๋ฌ์ค ํผ๋จ๋ฆฌ๊ธฐ
3. ์์ ์์ญ์ ๊ฐฏ์ ์ธ๊ธฐ
4. ๊ฐ์ฅ ํฐ ์์ ์์ญ ๊ตฌํ๊ธฐ
๋ด๊ฐ ๋ฐฐ์ด ๊ฒ
์์ ์ฌ๊ท
tmp_MAP[i][j] = 1;
make_wall(cnt + 1);
tmp_MAP[i][j] = 0;
์ด๋ ๊ฒ ์ฌ๊ท๋ฅผ ์ฐ๋ ๊ฑด ๋ด๊ฐ ์์ฃผ ์๋ ๊ธฐ๋ฒ ์ค์ ํ๋์ด๋ค. ์ ๊ธฐ์ตํด๋ฌ์ผ๊ฒ ๋ค.
์์ ๋ณต์ฌ(deep copy)
void copy(int (*target)[MAX], int (*dest)[MAX])
{
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
target[i][j] = dest[i][j];
}
2์ฐจ์ ๋ฐฐ์ด์ deep copyํ๋ ๊ฑธ ์ด๋ ๊ฒ ํ์๋ค๋. ์ด์ ์ค๋๋ง์ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ฑฐ, ์๋ฆ๋ต๊ฒ ํ์๋ ์๊ฐ์ ๋ 2์ค for๋ฌธ์ผ๋ก ๋๋ ธ๋ ๋ณต์ฌ๋ฅผ copy ํจ์๋ฅผ ๋ง๋ค์ด์ ํ๋ค. ๋ 2์ค for๋ฌธ์ผ๋ก๋ง ๋๋ ธ๋ ํ์, 2์ฐจ์ ๋ฐฐ์ด์ ๋งค๊ฐ๋ณ์๋ก ๋๊ธฐ๋ ๋ฒ์ ์์ ํ ๋ชจ๋ฅด๊ณ ์์๋ค. ๋ถ๋๋ฌ์ด ์ผ์ด๋ค.
์ ์ญ๋ณ์๋ฅผ ์ ์ด์ฉํ์
ํ๋ก๊ทธ๋๋จธ์ค๋ก ๋์ด๊ฐ๋ฉด์ ์๊พธ ์ ์ญ๋ณ์๋ฅผ ์ต์ํํ๊ณค ํ์๋ค. ๊ทธ๋ฌ๋๋ผ ํจ์ ๋ด์์ ์๊พธ ๋ณต์กํ๊ฒ ๋งค๊ฐ๋ณ์๋ฅผ ๋๊ฒจ์ฃผ๊ณ ๋ฐ๊ณ ์์ ํ๊ณ ํ๋ฉด์ ๋ณ์๊ฐ ์๋ํ์ง ์๋ ๊ฐ์ ๊ฐ๊ฒ ๋์์๋ค.
์ฝ๋ ์์ฑ์ ์ ์คํ, ํ์คํ๊ฒ
copy(virus_MAP,tmp_MAP)
์ ํด์คฌ์ด์ผ ํ๋๋ฐ, copy(virus_MAP,MAP)
์ผ๋ก ์
๋ ฅํด์ ํ์ฐธ์ ๋ต์ด ์๋์์๋ค. Print ๋ฌธ์ ์์ฑํด์ ๋ฐฐ์ด์ ์ถ๋ ฅํด ์ง์ ํ์ธํ๊ธฐ๊ฐ ๊ท์ฐฎ์์, ๋๋ฒ๊น
์ ํ๋๋ ์ธ์ ๋ ๊ทธ๋ ๋ฏ ๋ ์ค๋๊ฑธ๋ ธ๋ค. ์ค๊ณ๋ ๋จธ๋ฆฌ๊ฐ ํ๊ณ ๊ตฌํ์ ์๋
ธ๊ฐ๋ค๋ฅผ ๋ฐ์.
์ฝ๋
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 8;
int res;
int N, M;
int MAP[MAX][MAX];
int tmp_MAP[MAX][MAX];
void Print(int(*)[MAX]);
void copy(int (*target)[MAX], int (*dest)[MAX])
{
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
target[i][j] = dest[i][j];
}
bool isIn(int y, int x)
{
return (y >= 0 && y < N) && (x >= 0 && x < M);
}
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
void BFS()
{
queue<pair<int, int>> q;
int virus_MAP[MAX][MAX];
copy(virus_MAP, tmp_MAP);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (virus_MAP[i][j] == 2) q.push(make_pair(i, j));
while (!q.empty())
{
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int dy = y + dir[i][0];
int dx = x + dir[i][1];
if (isIn(dy, dx) && virus_MAP[dy][dx] == 0) {
virus_MAP[dy][dx] = 2;
q.push(make_pair(dy, dx));
}
}
}
int ans = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (virus_MAP[i][j] == 0) ans++;
res = max(res, ans);
return;
}
void make_wall(int cnt)
{
if (cnt == 3)
{
BFS();
return;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
if (tmp_MAP[i][j] == 0)
{
tmp_MAP[i][j] = 1;
make_wall(cnt + 1);
tmp_MAP[i][j] = 0;
}
}
}
void Print(int(*arr)[MAX])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cout << arr[i][j];
}
cout << endl;
}
return;
}
int main()
{
res = -1;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> MAP[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (MAP[i][j] == 0) {
copy(tmp_MAP, MAP);
tmp_MAP[i][j] = 1; //make wall
make_wall(1);
tmp_MAP[i][j] = 0;
}
}
}
cout << res;
return 0;
}
๋๋ฌด ๊ธธ๋ค.. ๋งํฌ๋ค์ด์๋ ํ ๊ธ์ด ์๋?