#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int map[310][310];
int mapCopy[310][310];
int visited[310][310];
int row, col;
int time;
queue<pair<int, int>> q;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int safe(int x, int y)
{
if(x >= 0 && y >= 0 && x < row && y < col)
{
return 1;
}
else
{
return 0;
}
}
void init()
{
for(int x = 0; x < row; x++)
{
for(int y = 0; y < col; y++)
{
int cnt = 0;
for(int k = 0; k < 4; k++)
{
int xpos = x+dx[k];
int ypos = y+dy[k];
if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0)
{
cnt++;
}
}
if(cnt != 0)
{
q.push({x, y});
}
}
}
}
void melt()
{
int size = q.size();
while(size--)
{
int x = q.front().first;
int y = q.front().second;
q.pop();
int cnt = 0;
for(int i = 0; i < 4; i++)
{
int xpos = x+dx[i];
int ypos = y+dy[i];
if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0)
{
cnt++;
}
}
mapCopy[x][y] -= cnt;
if(mapCopy[x][y] < 0)
{
mapCopy[x][y] = 0;
}
}
}
void check(int x, int y)
{
queue<pair<int, int>> c;
c.push({x, y});
visited[x][y] = 1;
while(!c.empty())
{
x = c.front().first;
y = c.front().second;
c.pop();
for(int i = 0; i < 4; i++)
{
int xpos = x+dx[i];
int ypos = y+dy[i];
if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 0 && visited[xpos][ypos] == 0)
{
c.push({xpos, ypos});
visited[xpos][ypos] = 1;
}
}
}
}
int main(void)
{
// freopen("B2589_input.txt", "r", stdin);
cin >> row >> col;
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
cin >> map[i][j];
mapCopy[i][j] = map[i][j];
}
}
while(1)
{
time++;
init();
melt();
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
map[i][j] = mapCopy[i][j];
}
}
int mapCnt = 0;
memset(visited, 0, sizeof(visited));
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
if(map[i][j] != 0 && visited[i][j] == 0)
{
check(i, j);
mapCnt++;
}
}
}
if(mapCnt >= 2)
{
cout << time;
break;
}
else if(mapCnt == 0)
{
cout << "0";
break;
}
}
return 0;
}
|
cs |
'Baekjoon > BFS' 카테고리의 다른 글
[백준 11559] Puyo Puyo (BFS) (C/C++) (★) (0) | 2019.12.08 |
---|---|
[백준 16234] 인구이동 (BFS) (C/C++) (★★) (0) | 2019.12.07 |
[백준 1389] 케빈 베이컨의 6단계 법칙 (BFS) (C/C++) (0) | 2019.12.06 |
[백준 1261] 알고스팟 (BFS) (C/C++) (★) (0) | 2019.12.06 |
[백준 14395] 4연산 (BFS) (C/C++) (0) | 2019.12.06 |