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

 

1) 문제설명

백준 Online Judge 2468번 안전 영역

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

2468번: 안전 영역

 

2) 아이디어

비가 오는 높이를 0~100까지 전부 반복문으로 돌리면서 BFS를 실행한다.

입력받은 영역이 비가오는 높이보다 크다면 1로 작으면 0으로 설정해주어서 단순화시킨다.

영역 배열을 하나 더 선언해 계속 입력받은 배열로 다시 초기화시켜주는 것이 중요하다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

int arr[102][102];
int visited[102][102];
queue<pair<int,int>> q;
int n;
int cnt = 0;
int maxt = 0;
void bfs(int x, int y) {
	
	q.push(make_pair(x, y));
	visited[x][y] = -1;
	cnt++;
	while (!q.empty()) {

		x = q.front().first;
		y = q.front().second;
		
		q.pop();
		int dx[] = { -1,1,0,0 };
		int dy[] = { 0,0,-1,1 };

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx<1 || ny<1 || nx>n || ny>n || visited[nx][ny] == 0) { // 범위를 넘어가거나 0이면 넘어가
				continue;
			}
			else {
				visited[nx][ny] = 0; // 방문처리
				q.push(make_pair(nx, ny));
			}
		}
	}
	
}

int main() {

	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j]; // 입력받고
			visited[i][j] = arr[i][j]; // 저장

		}
	}

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

		for (int i = 1; i <= n; i++) { // 다시 배열 처음으로 초기화
			for (int j = 1; j <= n; j++) {
				visited[i][j] = arr[i][j];
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (arr[i][j] > h) { // 배열이 h 보다 크다면 1
					visited[i][j] = 1;
				} 
				else { // 작다면 0
					visited[i][j] = 0;
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (visited[i][j] != 0) {
					bfs(i, j);
				}
			}
		}
		maxt = max(cnt, maxt);
		cnt = 0;
	}
	cout << maxt;
}