백준 2468번: 안전 영역

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

1. 문제

물에 잠기지 않는 영역을 구하는 문제

2. 알고리즘

키워드 - DFS, FloodFill

높이가 2 일때 다 잠긴다.

높이 3 일 때 안전한 영역 4개

높이 4 일 때 안전 영역 5개

높이 5 일 때 안전 영역 5개

높이 6 일 때 안정 영역 4 개

높이 7 일 때 안전 영역 2 개

높이 8 일 때 안전 영역 1

높이 9 일때 없다.

탐색할 노드의 값이 높이 보다 큰 경우 DFS 탐색 횟수를 카운트 하여 가장 많은 영역을 구한다.

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
using namespace std;
 
int n; 
 
int board[101][101];
int visited[101][101];
// 상 하 좌 우 
int dy[] = { 0, -1, 1, 0};
int dx[] = { -1, 0, 0, 1};
 
void dfs(int x, int y, int value) {
 
    visited[x][y] = 1;
 
    // 상 하 좌 우로 이동 하며 탐색 
    for (int i=0; i<4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
 
        // 배열의 인덱스를 넘지 않도록 
        if (ax < 0 || ay < 0 || ax >= n || ay >= n)             
            continue;
 
        if(visited[ax][ay] || board[ax][ay] <= value) 
            continue;
 
        dfs(ax, ay, value);
    }
}
 
int main() {
 
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n;
 
    int minvalue = 987654321;
    int maxvalue = 0;
 
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int d; cin >> d;
            board[i][j] = d;
            minvalue = min(minvalue, d);
            maxvalue = max(maxvalue, d);
        }
    }
 
    int sol = 1;
    for(int x=minvalue; x<=maxvalue; x++) {
 
        int cand = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
 
                if (!visited[i][j] && board[i][j] > x) {
                    cand++;
                    dfs(i, j, x); 
                }
            }
        }
 
        sol = max(sol, cand);
        memset(visited, 0, sizeof(visited));
    }
    cout << sol << "\n";
 
    return 0;
}