[백준/C++] 2468번 안전 영역

문제: www.acmicpc.net/problem/2468

2468번: 안전 영역

 

 

문제풀이

 

브루트포스와 BFS 알고리즘을 이용하여 문제를 풀었다.

 

비의 높이(h)에 대하여 h보다 높이가 높은 지대의 인접한 땅들의 영역 개수를 BFS로 구한다.

이때 h가 0부터 100일 때까지의 경우의 수 모두 비교한다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin>>n;

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

    int temp = 0;
    queue<pair<int,int>> q;
    for(int h=0; h<=100; h++){
        int area = 0; //영역 개수
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
            	//방문 했거나 지대가 h보다 낮은 지역은 continue
                if(visited[i][j]||board[i][j] <= h) continue;
				
                q.push({i,j});
                visited[i][j] = 1;
                area++; 영역 개수 증가

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

                    for(int dir=0; dir<4; dir++){
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];

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

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

            }
        }
        for(int i=0; i<n; i++) //다음 h를 위해 visited 배열 0 초기화
            fill(visited[i], visited[i]+n, 0);

        temp = max(temp, area); //영역 개수의 최대값
    }
    cout<<temp;
    
    return 0;
}

 

 

결과