[백준] 2468번 안전 영역 (= safe area) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/2468

#include <stdio.h>
#include <stdbool.h>

#define DEBUG 0
#define MAX_ROW_SIZE 100

typedef struct _Node {
    int height;
    bool visit;
    bool sink;
} Node;
Node arrInput[MAX_ROW_SIZE][MAX_ROW_SIZE];
int N;    //2차원 배열의 행과 열의 개수
int resultCount;    //안전한 영역의 개수

//비와서 잠긴 영역의 sink변수에 true 대입
//비오는 양은 증가하기만 하므로 한 번 잠기면 더 이상 그 영역 탐색 안함
void raining(int);
void countArea(void);    //i만큼 비가 왔을 때 잠기지 않은 영역의 개수 계산
void visit(int, int);    //인자로 입력된 영역과 연결된 모든 잠기지 않은 영역의 방문 체크
#if DEBUG
    void printVisit(void);
    void printSink(void);
#endif

int main(void)
{
    int maxHeight = 1;    //안전한 영역의 최대 높이

    //input 값 저장
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &arrInput[i][j].height);
            //안전한 영역의 최대 높이 갱신
            maxHeight = arrInput[i][j].height > maxHeight ? arrInput[i][j].height : maxHeight;
            arrInput[i][j].visit = false;
            arrInput[i][j].sink = false;
        }
    }
    resultCount = 1;    //아무 곳도 잠기지 않으면 안전한 영역 1개

    //비오는 양 i
    for (int i = 1; i < maxHeight; i++) {
        raining(i);    //비와서 잠긴 영역은 sink 변수에 true 대입하고 앞으로 탐색 안함
        countArea();    //i만큼 비가 왔을 때 잠기지 않은 안전한 영역의 개수 계산
    }

    printf("%d\n", resultCount);

    return 0;
}

void raining(int rainHeight)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //현재 땅이 이미 잠겨있다면 확인할 필요가 없음
            if (arrInput[i][j].sink) {
                continue;
            }
            //현재 땅이 잠겨있지 않은데 현재 내린 비보다 높지 않으면 잠긴다
            if (arrInput[i][j].height <= rainHeight) {
                arrInput[i][j].sink = true;
            }
        }
    }
}

void countArea(void)
{
    int count = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            //현재 땅이 잠겨있지 않고 && 방문한 적이 없으면 안전한 영역 count한다
            if (!arrInput[i][j].sink && !arrInput[i][j].visit) {
                count++;
                visit(i, j);
            }
        }
    }
    //최대 영역 개수 갱신
    if (count > resultCount) {
        resultCount = count;
    }
    //다음 높이 입력값 때 안전 영역 개수를 count 하기 위해서 visit을 false로 바꿈
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            arrInput[i][j].visit = false;
        }
    }
    return;
}

void visit(int x, int y)
{
    arrInput[x][y].visit = true;

    //오른쪽 영역이 존재하고 && 물에 잠기지 않고 && 잠기지 않았는지 방문 안했으면
    if (++x < N && !arrInput[x][y].sink && !arrInput[x][y].visit) {
        visit(x, y);
    }
    x--;
    //왼쪽 영역이 존재하고 && 물에 잠기지 않고 && 잠기지 않았는지 방문 안했으면
    if (--x >= 0 && !arrInput[x][y].sink && !arrInput[x][y].visit) {
        visit(x, y);
    }
    x++;
    //위쪽 영역이 존재하고 && 물에 잠기지 않고 && 잠기지 않았는지 방문 안했으면
    if (++y < N && !arrInput[x][y].sink && !arrInput[x][y].visit) {
        visit(x, y);
    }
    y--;
    //아래쪽 영역이 존재하고 && 물에 잠기지 않고 && 잠기지 않았는지 방문 안했으면
    if (--y >= 0 && !arrInput[x][y].sink && !arrInput[x][y].visit) {
        visit(x, y);
    }
    y++;
    return;
}
#if DEBUG
void printVisit(void)
{
    printf("printVisit\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", arrInput[i][j].visit);
        }
        printf("\n");
    }
    printf("\n");
    return;
}
void printSink(void)
{
    printf("printSink\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", arrInput[i][j].sink);
        }
        printf("\n");
    }
    printf("\n");
    return;
}
#endif