[백준/BOJ] - 2468번 안전 영역 (C++/DFS)

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

 

 

 

 

 

01. 문제

---

 

 

 

 

 

 

문제설명

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 

 

---

 

 

02. 문제 접근 과정 📖

먼저 이 문제는
김동빈 저자의 
이것이 코딩테스트다 책 
의 나오는 149페이지의 나오는 얼음료수 얼려 먹기 문제랑 똑같이 풀면 될 것 같다.

비의 높이는 최대 0~100이다.

알고리즘은 DFS를 사용해서 주변 칸 들을 계산하면 될 것 같다.

 

 

---

 

03. 문제 풀이 ✏️

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;


int N;

int graph[200][200];
int realMap[200][200] { 0,};


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


bool dfs(int x, int y, int water)
{
    if(x <= -1 or x >=N or y <= -1 or y >= N)
    {
        return false;
    }


    if(graph[x][y] > water)
    {
        graph[x][y] = -1;

        dfs(x - 1, y, water);
        dfs(x + 1, y, water);
        dfs(x , y+1, water);
        dfs(x , y-1, water);

        return true;
    }
    return false;
}

int main()
{
    cin >> N;

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

    int max = 0;
    int sum = 0;

    for (int h = 0; h <= 100; h++)
    {
        int heightCount = 0;

        memcpy(graph, realMap, sizeof(realMap));


        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if(dfs(i, j, h))
                {
                    ++heightCount;
                }
            }
        }

        if(heightCount > max)
        {
            max = heightCount;
        }


    }

    cout << max << endl;

    return 0;
}

 

 

이런 느낌으로 풀면 된다...

 

---

04. 결론