[백준 2486번 C++] Silver1. 안전 영역

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

핵심 아이디어 및 정답 코드

- 특정 높이 이상의 인접한 영역을 묶었을 때 가장 많은 영역으로 쪼개지는 경우를 구하는 문제

- 깊이 우선 탐색(DFS) 알고리즘을 이용하여 최소 ~ 최대 범위에서 가장 많은 영역이 생기는 경우를 구함

+ BFS로 풀어도 무관해보이지만, 모든 경우를 구해야 하므로 DFS가 더 유리할 수 있음

 

+ Memo) Find-Union 알고리즘 + a 로 한번 풀어볼 것 ( 시간 복잡도를 많이 줄일 수 있음 )

 -> 20ms -> 0ms

 

DFS 풀이 정답 코드

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

#include <iostream>

using namespace std;

int intArrays[101][101] = { 0 };
bool boolArrays[101][101] = { false };
int dirX[4] = { 1, -1, 0, 0 };
int dirY[4] = { 0, 0, 1, -1 };
int answer;
int maxSize;

void ClearBoolArrays()
{
    for (int y = 0; y < maxSize; y++)
        for (int x = 0; x < maxSize; x++)
            boolArrays[y][x] = false;
}

void DFS(int y, int x, int cost)
{
    boolArrays[y][x] = true;
    for (int i = 0; i < 4; i++)
    {
        int movePosY = y + dirY[i];
        int movePosX = x + dirX[i];

        if (movePosY < 0 || maxSize <= movePosY
            || movePosX < 0 || maxSize <= movePosX
            || boolArrays[movePosY][movePosX])
            continue;

        if (intArrays[movePosY][movePosX] > cost)
            DFS(movePosY, movePosX, cost);
    }
}

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

    answer = 1;
    cin >> maxSize;
    int maxValue = 0;
    for (int y = 0; y < maxSize; y++)
    {
        for (int x = 0; x < maxSize; x++)
        {
            cin >> intArrays[y][x];
            if (maxValue < intArrays[y][x])
                maxValue = intArrays[y][x];
        }
    }

    for (int i = 1; i <= maxValue; i++)
    {
        int count = 0;
        for (int y = 0; y < maxSize; y++)
        {
            for (int x = 0; x < maxSize; x++)
            {
                if (boolArrays[y][x])
                    continue;

                if (intArrays[y][x] > i)
                {
                    count++;
                    DFS(y, x, i);
                }
            }
        }

        if (answer < count)
            answer = count;

        ClearBoolArrays();
    }

    cout << answer;
    return 0;
}