2573번 빙산

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

DFS, dy + dx 활용 문제이다.

지구온난화가 발생하기 전에, isZero() 함수를 통해 전체 Map이 0인지 아닌지 검사를 하고,

연결 요소의 개수를 검사한다.

이후에 지구온난화가 발생하고, 그에 따른 높이가 낮아지게 된다.

예전에 푼 코드를 보니, 그 때에는 [303][303] 크기의 배열을 2개로 선언하여,

지구온난화가 발생했을 때, 이중 for문에서의 배열과, 0의 개수를 세는 for문에서의 배열을 다르게 하여

서로 영향을 미치지 않게 했다.

즉, 2와 4가 붙어있다고 했을 때, 2의 주변에 0의 개수가 2개라면, 0이 될 것이고, 

4의 주변에 0의 개수를 검사했을 때, 2가 0이 된 것을 포함시키면 안 된다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int Map[303][303] = { 0, };
 
int N = 0, M = 0;
 
bool visit[303][303] = { false, };
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
vector<int> v;
 
bool isZero()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            if (Map[i][j] != 0) return false;
        }
    }
 
    return true;
}
 
void DFS(int r, int c)
{
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x] || Map[y][x] == 0) continue;
 
        DFS(y, x);
    }
}
 
void globalWarming(int r, int c)
{
    int Cnt = 0;
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= N || x < 0 || x >= M || Map[y][x] != 0) continue;
 
        if(Map[y][x] == 0) ++Cnt;
    }
 
    v.push_back(Cnt);
}
 
int main(void)
{
    memset(Map, 0, sizeof(Map));
 
    bool Zero = false;
    int year = 0;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &Map[i][j]);
        }
    }
 
    while (1)
    {
        int Connected_Component = 0;
        if (!v.empty()) v.clear();
        memset(visit, false, sizeof(visit));
 
        if (isZero())
        {
            Zero = true;
            break;
        }
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (!visit[i][j] && Map[i][j] != 0)
                {
                    ++Connected_Component;
 
                    DFS(i, j);
                }
            }
        }
 
        if (Connected_Component >= 2) break;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (Map[i][j] != 0)
                {
                    globalWarming(i, j);
                }
            }
        }
 
        int index = 0;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (Map[i][j] != 0)
                {
                    Map[i][j] -= v.at(index++);
 
                    if (Map[i][j] < 0) Map[i][j] = 0;
                }
            }
        }
 
        ++year;
    }
    
    if (Zero) printf("0\n");
    else printf("%d\n", year);
 
    return 0;
}