DFS 문제 분석-4(안전영역 boj_2468)

1. 안전영역 문제 분석(boj.kr/2468)

이 문제는 처음에 낚였다. 왜 height=0, height=maxH일때를 왜 생각하는 건가?

솔직히 아직도 잘 모르겠다. 높이가 최대이면, 다 잠겨버리는거 아닌가? 그래서 고려할 가치가 없다고 생각했다.

하지만, 높이가 0일때는 구분해야한다. 왜냐면, 전부 높이가 1인 경우가 있기 때문이다.

약간 문제의 낚시라고 해야하나 문제 자체는 쉬웠는데, 저 부분에서 좀 애먹었다. 

#include <stdio.h>
#include <string.h>
 
#define MAX_SIZE 101
 
int row[4] = { -1, 0, 1, 0 };
int col[4] = { 0, -1, 0, 1 };
int map[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE][MAX_SIZE];
int N;
 
int checkRangeOver(int i, int j) {
    return !(i >= N || i < 0 || j >= N || j < 0) ? 1 : 0;
}
 
void dfs(int i, int j, int height) {
    visited[i][j] = 1;
 
    for (int a = 0; a < 4; ++a) {
        int row_y = row[a] + i;
        int col_x = col[a] + j;
 
        if (checkRangeOver(row_y, col_x) && map[row_y][col_x] > height
            && !visited[row_y][col_x]) {
            dfs(row_y, col_x, height);
        }
    }
}
 
int main(void) {
    int cnt = 0;
    int maxCnt = 1;
    int maxH = 0;
 
    scanf("%d", &N);
    
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d ", &map[i][j]);
            if (maxH < map[i][j]) maxH = map[i][j];
        }
    }
 
    for (int height = 0; height <= maxH; ++height) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (!visited[i][j] && map[i][j] > height) {
                    dfs(i, j, height);
                    cnt++;
                }
            }
        }
 
        if (maxCnt < cnt) maxCnt = cnt;
        cnt = 0;
        memset(visited, 0, sizeof(visited));
    }
 
    printf("%d\n", maxCnt);
    
    return 0;
}