백준 : 2468번 안전 영역 BFS(c++)

프로그래머스 링크

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

2468번: 안전 영역

코드 풀이

BFS를 활용하여 풀이하였습니다.

기본적으로 물에 잠기는 깊이를 증가하며 매번 탐색을 진행

벡터와 큐페어, 구역카운트는 매번 초기화가 진행되어야 해서 탐색 for문 밖에다가 선언을 해주었다.

지역을 돌면서 탐색을 진행하는데 물에 잠긴곳은 판단하지 않고 continue로 넘겨주었고 마찬가지로 방문한 노드도 continue로 넘겨주었다.

이후 다른 BFS방식이랑 동일합니다.

즉 이번 문제를 풀때 잘 생각해야 하는 부분은 물 잠기는 깊이에 따라 맥스치의 구역 카운트를 갱신해주는것과 잠기는곳의 예외처리정도만 잘 생각하고 풀면 쉽게 풀 수 있는 문제 같습니다.

코드

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

using namespace std;

int Board[101][101];

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

int N, Max;
int Deep = 0;

int MaxArea;

void BFS()
{
    // 물의 깊이에 따른 탐색
    while (Deep < Max)
    {
        // 방문 벡터와 queuePair, AreaCount는 매번 새로 초기화 해야하기 때문에 아래에 선언
        vector<vector<bool>> vecIsVisit(N, vector<bool>(N));

        queue<pair<int, int>> qPair;
        int AreaCount = 0;

        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                // 예외처리
                if (vecIsVisit[i][j] || Board[i][j] - Deep <= 0)
                    continue;

                qPair.push({ i, j });

                vecIsVisit[i][j] = true;

                ++AreaCount;
                MaxArea = max(MaxArea, AreaCount);

                while (!qPair.empty())
                {
                    pair<int, int> Cur = qPair.front();
                    qPair.pop();

                    for (int Dir = 0; Dir < 4; ++Dir)
                    {
                        int NextX = Cur.second + dx[Dir];
                        int NextY = Cur.first + dy[Dir];

                        // 범위 밖 예외처리 1
                        if (NextX < 0 || NextY < 0 || NextX >= N || NextY >= N)
                            continue;

                        // 가면 안되는곳 예외처리 2
                        if(Board[NextY][NextX] - Deep <= 0 || vecIsVisit[NextY][NextX] == true)
                            continue;

                        vecIsVisit[NextY][NextX] = true;
                        qPair.push({ NextY, NextX });
                    }
                }
            }
        }
        // Deep 깊이 1증가
        ++Deep;
    }
}

int main()
{
    cin >> N;

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

    BFS();

    cout << MaxArea;

    return 0;
}