[BOJ] 안전영역

[문제]

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

2468번: 안전 영역

[풀이]

2468

맞았습니다!!

2208

16

C++14 / 수정

1200

58초 전

 

1) k보다 낮은 영역들은 사전에 방문표시를 한다. 

 

2) 아직 방문하지 않았고 k보다 높은 영역들을 dfs로 탐색하면서 영역의 개수를 늘려준다.

(안전영역 : 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다)

 

3) 최대값을 구한다. 

 

---

#include <iostream>
#include <cstring>
 
using namespace std;
 
//안전영역
int n, map[101][101];
bool visited[101][101];
 
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1, 0,0};
void dfs(int x, int y) {
    visited[x][y] = true;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
 
        dfs(nx, ny);
    }
 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    int max_h = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
            if (max_h < map[i][j])
                max_h = map[i][j];
        }
    } //input
 
    int max_cnt = 1;
    for (int k = 1; k <= max_h; k++)
    {
        memset(visited, false, sizeof(visited));
        int cnt = 0;
 
        //k보다 낮은 높이의 영역들은 true로 표시
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (map[i][j] <= k)
                {
                    visited[i][j] = true;
                }
            }
        }
 
        //영역 탐색
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!visited[i][j] && map[i][j] > k) {
                    ++cnt;
                    dfs(i, j);
                }
                if (cnt > max_cnt) max_cnt = cnt;
            }
        }
    }
    cout << max_cnt << '\n';
    return 0;
}