백준 2468번 안전 영역 문제 풀이 C++

🔷 백준 2468번: 안전 영역 (DFS, 스택 사용)

문제 링크 바로가기 🔗

🔷 문제 요약

장마철에 어떤 지역에 비가 왔을 때, 일정 높이 이하의 지점은 물에 잠긴다고 가정합니다.
이때, 물에 잠기지 않고 연결되어 있는 지점들을 하나의 안전 영역이라고 할 때,
모든 강수량 상황에 대해 물에 잠기지 않는 안전 영역의 최대 개수를 구하는 문제입니다.

---

🔷 문제 조건 요약

• 지도는 N x N의 2차원 배열
• 각 칸에는 1~100 사이의 높이 정보가 있음
• 비의 양이 증가할수록 낮은 지점부터 잠김
• 잠기지 않은 지점 중 상하좌우로 연결된 구역이 하나의 안전 영역

---

🔷 나의 풀이 접근법

1. 기본 전략

• 비의 양을 0부터 100까지 바꾸어가며 시뮬레이션
• 각 강수량마다 안전한 지역을 DFS로 탐색
• 탐색한 영역은 방문 처리 (check 배열)
• 각 강수량에서 탐색한 영역의 개수를 세고, 최대값을 저장

2. DFS 방식 선택

• 재귀보다 스택 기반 DFS를 직접 구현
• 반복문 안에 while (!stack.empty())를 통해 탐색
• pop한 위치에서 상하좌우로 이동 가능한 곳을 계속 push

3. 흐름 요약

1. k = 0~100 반복 → 비의 높이 설정
2. 안전한 위치에서 DFS 시작
3. 연결된 안전 지대 전부 탐색 → 하나의 안전 영역
4. 카운트하고 최댓값 갱신

---

🔷 처음 작성한 코드

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

struct Point{
    int x;
    int y;
};

int main(void)
{
    int N;
    int arr[101][101];
    int cnt=0, max_rain=-1;
    stack<Point> stc;
    cin >> N;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> arr[i][j];

    for(int k=0; k<=100; k++)
    {
        cnt = 0;
        int check[101][101] = {0};  // 방문 여부 초기화

        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(arr[i][j] > k && check[i][j] == 0)
                {
                    stc.push({i,j});
                    check[i][j] = 1;

                    while(!stc.empty())
                    {
                        Point cur = stc.top(); stc.pop();
                        int x = cur.x, y = cur.y;

                        // 상
                        if (x - 1 >= 0 && arr[x - 1][y] > k && check[x - 1][y] == 0)
                            stc.push({x - 1, y}), check[x - 1][y] = 1;

                        // 하
                        if (x + 1 < N && arr[x + 1][y] > k && check[x + 1][y] == 0)
                            stc.push({x + 1, y}), check[x + 1][y] = 1;

                        // 좌
                        if (y - 1 >= 0 && arr[x][y - 1] > k && check[x][y - 1] == 0)
                            stc.push({x, y - 1}), check[x][y - 1] = 1;

                        // 우
                        if (y + 1 < N && arr[x][y + 1] > k && check[x][y + 1] == 0)
                            stc.push({x, y + 1}), check[x][y + 1] = 1;
                    }

                    cnt++; // 하나의 안전 구역 탐색 완료
                }
            }
        }

        if(cnt > max_rain)
            max_rain = cnt;
    }

    cout << max_rain << endl;
    return 0;
}

---

🔷 코드 파트별 설명

파트	설명
struct Point	좌표 정보를 저장하는 구조체
arr[N][N]	지역의 높이 정보 저장
check[N][N]	해당 위치가 방문되었는지 체크
for k in 0~100	강수량을 바꿔가며 시뮬레이션
stack DFS	연결된 안전지역을 한 덩어리로 탐색
cnt	현재 강수량에서의 안전 지역 개수
max_rain	지금까지 찾은 최대 안전 지역 수

---

🔷 안전 영역 풀이 (2부) - 수정 과정 & 개선점

🧩 디버깅 & 수정 과정

✅ 1. check 배열 초기화 누락

처음 코드에서는 check 배열을 한 번만 선언하고, 다음 강수량에서도 초기화하지 않아
이전 강수량에서 방문 처리한 정보가 계속 남아 있었음 → 영역 수가 줄어드는 버그 발생

해결 방법:
int check[101][101] = {0}; // 매 강수량마다 새롭게 선언하여 자동 초기화

✅ 2. DFS 내부 조건에서 > 4로 고정된 실수

처음 구현한 DFS 탐색에서 비교 조건이
arr[x ± 1][y] > 4 // ❌ 고정된 값
으로 고정되어 있어서, 실제 강수량 k와 상관없이 탐색이 잘못됨

해결 방법:
arr[x ± 1][y] > k // ✔️ 현재 비의 높이에 맞게 비교

---

🔷 개선 방향 및 리팩터링

🔁 1. 코드 중복 제거: 상하좌우 방향 배열로 처리

현재는 상하좌우 각각 조건을 4번 써서 비교하고 있음
→ dx, dy 배열로 간단히 반복문 하나로 묶을 수 있음

개선 코드 일부:

int dx[4] = {-1, 1, 0, 0};  // 상, 하, 좌, 우
int dy[4] = {0, 0, -1, 1};

for (int d = 0; d < 4; d++) {
    int nx = x + dx[d];
    int ny = y + dy[d];
    if (nx >= 0 && nx < N && ny >= 0 && ny < N &
        arr[nx][ny] > k && check[nx][ny] == 0) {
        stc.push({nx, ny});
        check[nx][ny] = 1;
    }
}

⏱ 2. 시간 최적화: 최대 높이까지만 반복

비가 아무리 많이 와도, 지역에서 가장 높은 지점 이상으로는 의미 없음
→ 굳이 k = 0 ~ 100까지 돌 필요 없이, 지역 내 최댓값까지만 돌면 충분

개선 코드:

int max_height = 0;
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        max_height = max(max_height, arr[i][j]);

for (int k = 0; k <= max_height; k++) {
    // 안전 구역 탐색 수행
}

---

✅ 개선된 최종 코드 (리팩터링 포함)

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

struct Point { int x, y; };

int N, arr[101][101];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    cin >> N;
    int max_h = 0;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            max_h = max(max_h, arr[i][j]);
        }

    int max_safe = 0;

    for (int k = 0; k <= max_h; k++) {
        bool check[101][101] = {false};
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] > k && !check[i][j]) {
                    stack<Point> st;
                    st.push({i, j});
                    check[i][j] = true;

                    while (!st.empty()) {
                        Point cur = st.top(); st.pop();
                        for (int d = 0; d < 4; d++) {
                            int nx = cur.x + dx[d];
                            int ny = cur.y + dy[d];
                            if (nx >= 0 && nx < N && ny >= 0 && ny < N &&
                                arr[nx][ny] > k && !check[nx][ny]) {
                                st.push({nx, ny});
                                check[nx][ny] = true;
                            }
                        }
                    }

                    cnt++;
                }
            }
        }

        max_safe = max(max_safe, cnt);
    }

    cout << max_safe << endl;
    return 0;
}

---

🔷 마무리 정리

• DFS 스택으로 안전영역 탐색 성공 ✅
• check 배열 초기화, 비교값 오류 수정 ✅
• 리팩터링으로 코드 간결화, 효율성 개선 ✅

---