[백준 2573]빙산

문제: https://www.acmicpc.net/problem/2573

1)문제 분류

-BFS

-DFS

2)해결방안

- 백준문제중 '치즈'문제와 유사하다.

 -0(바다)부분만 큐에 집어 넣는다.

  1년 후 얼마나 녹을지에 대한 정보를 담은 새 맵을 만든다.

  바다를 넣은 큐를 꺼내면서 4방향 (동서남북) 탐색하며 빙산이 있다면, 새 맵에 카운트를 센다.

 (빙산 기준에서 주위 4방향에 바다가 얼마나 있는지를 카운트하는 것 )

- 큐를 다 돌린 후, 현재 맵에서, 아까 만든 새 맵의 카운트를 빼준다.(빙산이 녹은 1년 후의 맵을 다시 그리는 것)

- 현재맵에서 빙산이 녹아 바다가 된(0이 된) 부분이 존재한다.

 -그 부분까지 포함해서 다시 큐를 돌리면된다.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

int n, m,Time;

int map[302][302];

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

typedef struct Data {

int x, y, cnt;

}Data;

queue<Data>sea;

bool range(int rx, int ry)

{

if (rx<0 || ry<0 || rx>n - 1 || ry>m - 1)return false;

else return true;

}

int melt()

{

int ok = 0;

int after[302][302] = {0,};

//바다 지점에서 각 4방향씩 검사

while (!sea.empty())

{

Data output = sea.front();

sea.pop();

//cout << output.x << " " << output.y << endl;

for (int i = 0; i < 4; i++)

{

Data input;

input.x = output.x + xrr[i];

input.y = output.y + yrr[i];

if (range(input.x, input.y) && map[input.x][input.y] != 0)

{

after[input.x][input.y]++; //빙산지점 녹여야할 카운트

}

}

}

//녹이기 

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (map[i][j] == 0) {

sea.push({ i,j,0 }); //녹인 후 바다가 된 부분 삽입 

continue;

}     

int a=map[i][j]-after[i][j];

if (a <= 0)

{

map[i][j] = 0;

sea.push({ i,j,0 }); //녹인 후 바다가 된 부분 삽입 

}

else

{

map[i][j] = a;

ok = 1; //빙산 아직 있음

}

}

}

return ok;

}

int chk()

{   

int ok = 0;

bool visited[302][302] = { 0,0, };

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (map[i][j] != 0 && visited[i][j] == false)

{

ok++;

visited[i][j] = true;

queue<Data>temp;

temp.push({ i,j,0});

while (!temp.empty())

{

Data output = temp.front();

temp.pop();

for (int d = 0; d < 4; d++)

{

Data input;

input.x = output.x + xrr[d];

input.y = output.y + yrr[d];

if (range(input.x, input.y) && visited[input.x][input.y] == false && map[input.x][input.y] != 0)

{

visited[input.x][input.y] = true;

temp.push({ input.x,input.y,0 });

}

}

}

}

}

}

if (ok >= 2)

{

return 1; //분리됨 

}

else 

return 0;

}

int main()

{

cin >> n >> m;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

cin >> map[i][j];

if (map[i][j] == 0)

sea.push({ i,j,0 });

}

}

while (1)

{

if (chk() == 1) //분리됬는지 검사

{

cout << Time << endl;

return 0;

}

Time++; //1년씩 지남 

if (melt() == 0)

{

cout << 0 << endl;

return 0;

}

}

}