2468번 안전 영역

연결 요소를 구하는 기본 문제이다.

예외 상황이 모두가 같은 높이이면 '1'을 출력하면 되는데(map 전체가 하나),

처음에는 아래 처럼 생각했었다.

    if (min_num == max_num)
    {
        printf("1\n");
 
        return 0;
    }

그러나, 다시 한 번 생각해보니

이 문제에서 요구하는 답(연결 요소)의 최솟값은 1이기 때문에

result를 1로 선언하였다.

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
#define WATER_FULL 987654321
 
using namespace std;
 
int  map[102][102] = { 0, };
 
int N = 0;
 
int min_num = 987654321;
int max_num = -987654321;
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
bool visit[102][102] = { false, };
 
void water(int w)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == w)
            {
                map[i][j] = WATER_FULL; // 물에 잠김
            }
        }
    }
}
 
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 (0 <= y && y < N && 0 <= x && x < N && !visit[y][x] && map[y][x] != WATER_FULL)
        {
            DFS(y, x);
        }
    }
}
 
int main(void)
{
    int result = 1;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &map[i][j]);
 
            min_num = min(min_num, map[i][j]);
            max_num = max(max_num, map[i][j]);
        }
    }
 
    for (int i = min_num; i <= max_num; i++)
    {
        int Connected_Component = 0;
 
        memset(visit, false, sizeof(visit));
 
        water(i);
 
        for (int r = 0; r < N; r++)
        {
            for (int c = 0; c < N; c++)
            {
                if (!visit[r][c] && map[r][c] != WATER_FULL)
                {
                    ++Connected_Component;
 
                    DFS(r, c);
                }
            }
        }
        
        result = max(result, Connected_Component);
    }
 
    printf("%d\n", result);
 
    return 0;
}