[BOJ알고리즘, C++]#2468_안전 영역, 그래프 탐색, DFS, BFS, 미로 탐색

 

#1. 문제

2468번: 안전 영역

 

---

 

#2. 풀이

 

1. 그래프 탐색

[자료구조]#6_그래프

 

그래프의 모든 정점을 탐색하는 방법은 두 가지입니다. 먼저, DFS(깊이 우선 탐색)은 출발 정점으로부터 더 이상 확장할 수 없는 단말 노드까지 먼저 탐색하는 방법입니다. DFS는 일반적으로 재귀 호출 혹은 스택을 활용하여 구현합니다. 다음으로, BFS(너비 우선 탐색)은 현재 정점과 인접한 정점들을 우선 탐색하는 방법입니다. BFS는 일반적으로 큐를 활용하여 구현합니다.

 

2. 전형적인 미로 찾기 + 조건 추가 문제

 

1. BFS를 수행하는 그래프 탐색을 구현합니다.
2. 이때, 기준 높이를 인자로 추가적으로 전달하여, 해당 기준 높이 보다 높이 값이 높은 영역들을 카운트해 줍니다.

 

---

 

#3. 코드

 

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

typedef pair<int, int> p;

int N, res;
vector<vector<int>> heights;
vector<vector<bool>> visited;

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

void bfs(p start, int h)
{
    queue<p> q;

    visited[start.first][start.second] = true;
    q.push(start);

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx] || heights[ny][nx] <= h)
                continue;

            q.push({ny, nx});
            visited[ny][nx] = true;
        }
    }
}

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

    cin >> N;

    heights.resize(N, vector<int>(N));

    int maxHeight = -1;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> heights[i][j];
            maxHeight = max(maxHeight, heights[i][j]);
        }
    }

    for (int h = 0; h <= maxHeight; ++h)
    {
        visited.clear();
        visited.resize(N, vector<bool>(N, false));
        int cnt = 0;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                if (!visited[i][j] && heights[i][j] > h)
                {
                    bfs({i, j}, h);
                    cnt++;
                }
            }
        }
        res = max(res, cnt);
    }

    cout << res;

    return 0;
}

 

---