[Baekjoon(백준)][2468번] 안전 영역(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "안전 영역" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 주어진 지역의 높이 정보를 기반으로 장마철에 비가 내렸을 때 생기는 물에 잠기지 않는 안전한 영역의 최대 개수를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

2468번: 안전 영역

문제 개요

"안전 영역" 문제는 주어진 지역의 높이 정보를 기반으로 장마철에 비가 내렸을 때 생기는 물에 잠기지 않는 안전한 영역의 최대 개수를 찾는 문제입니다. 각 지점의 높이 정보가 주어지고, 물의 높이에 따라 잠기는 지역이 결정됩니다. 각 지점은 상하좌우로만 이동할 수 있으며, 안전 영역은 물에 잠기지 않은 인접한 지점들의 집합입니다.

해결 방법

이 문제는 깊이 우선 탐색(DFS)을 사용하여 해결합니다. 물의 높이를 1부터 100까지 변화시키며 각 경우에 대해 DFS를 수행합니다. 이 과정에서 방문하지 않은 고지대(물에 잠기지 않은 지역)에서 시작하여 상하좌우로 연결된 모든 고지대를 탐색하며 안전 영역의 개수를 세어냅니다.

코드 구현

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n; // 지역의 크기
int table[105][105]; // 높이 정보
bool visited[105][105]; // 방문 여부
int dy[] = { -1,0,1,0 }; // 상하좌우 이동
int dx[] = { 0,1,0,-1 }; // 상하좌우 이동

// dfs 함수: 특정 지점에서 시작하여 안전 영역 탐색
void dfs(int y, int x, int height) {
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        // 범위 체크 및 물에 잠기지 않은 지역 탐색
        if (ny >= 0 && nx >= 0 && ny < n && nx < n && !visited[ny][nx] && table[ny][nx] > height) {
            dfs(ny, nx, height);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n; // 지역의 크기 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> table[i][j]; // 높이 정보 입력
        }
    }

    int ret = 1; // 안전 영역의 최대 개수 (물에 잠기지 않는 경우 포함)
    for (int d = 1; d <= 100; d++) { // 물의 높이에 따라 탐색
        fill(&visited[0][0], &visited[0][0] + 105 * 105, false);
        int count = 0; // 안전 영역 개수
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (table[i][j] > d && !visited[i][j]) { // 물에 잠기지 않은 지점 탐색
                    dfs(i, j, d);
                    count++;
                }
            }
        }
        ret = max(ret, count); // 최대 안전 영역 개수 갱신
    }
    cout << ret << "\n"; // 결과 출력
    return 0;
}

코드 설명

이 코드는 물의 높이에 따른 안전 영역의 변화를 탐색하여 안전 영역의 최대 개수를 찾습니다. ret 변수는 안전 영역의 최대 개수를 저장하는데, 이를 1로 초기화하는 이유는 비가 전혀 오지 않는 경우(모든 지점이 안전 영역이 되는 경우)도 고려하기 위함입니다. 각 물의 높이에 대해 안전 영역의 수를 세고, 이 중 최대값을 ret에 저장하여 출력합니다.

결론

"안전 영역" 문제는 다양한 높이의 물에 의해 형성되는 안전 영역의 변화를 이해하고, DFS 알고리즘을 통해 이를 효과적으로 탐색하는 능력을 요구합니다. 비가 오지 않는 경우도 고려하여 안전 영역의 최대 개수를 정확히 파악하는 것이 중요합니다.