문제

문제링크

해설

• 시키는대로 하면 되는 문제입니다만, 한 가지 반례를 생각해야 하는 점이 조금 까다로운 문제입니다.
  • 바로, '비가 내리지 않을 수도 있다'는 점이 문제에 숨겨져 있다는 점입니다.
  • 따라서 모든 경우의 수를 검사할 때 비를 의미하는 반복문의 시작은 1이 아니라 0부터 시작해야 합니다.
• 최대 100 × 100 배열이고 검사할 높이도 100이므로 최악의 경우 100만 번 검사하므로 충분히 bruteforce + DFS/BFS로 시간 내에 풀 수 있습니다.
• 프로그램 연산 효율을 위해
  • 실제로 지도에서 비가 내린 것을 반영 (각 칸마다 뺄셈연산)하는 것 보다는 비교연산 하는 게 낫습니다.
  • memset() 함수를 이용해서 visited 배열을 초기화합니다.

코드

#include <iostream>
#include <cstring>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int N, city[102][102];
bool visited[102][102];

void dfs(int y, int x, const int& h) {
    visited[y][x] = true;
    for (auto i : d) {
        int ny = y + i[0], nx = x + i[1];
        if (city[ny][nx] > h && !visited[ny][nx]) dfs(ny, nx, h);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N;

    int max_height = 0;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cin >> city[y][x];
            max_height = max(max_height, city[y][x]);
        }
    }
    int answer = 0;
    for (int h = 0; h <= max_height; h++) {
        int result = 0;
        for (int y = 1; y <= N; y++)
            for (int x = 1; x <= N; x++)
                if (city[y][x] > h && !visited[y][x])
                    dfs(y, x, h), result++;
        answer = max(answer, result);
        memset(visited, false, sizeof(visited));
    }
    cout << answer << '\n';
    return 0;
}

소스코드 링크

결과