[BOJ] C++ 2468 "안전 영역" 문제 풀이 _ nov

#INFO

난이도 : SILVER1

문제유형 : BFS

출처 : 2468번: 안전 영역 (acmicpc.net)

2468번: 안전 영역

---

#SOLVE

특정한 높이에서 물에 잠기지 않은 영역의 최대 개수를 구하는 문제이다. 예를들어 높이가 3 이하인 모든 지점이 물에 잠겼다고 가정하면 아래 그림과 같이 4가지 구역으로 나뉘어 진다. 

높이가 0부터 보드 내에서 가장 큰 높이인 9까지 모든 경우의 수를 탐색해 가장 나뉘어지는 구역이 많은 케이스를 선택하는 브루트포스 방식으로 문제를 풀이했다.

#define X first
#define Y second
int board[103][103]; // 물의 높이를 저장할 배열
int rain[103][103]; // 1 : 물에 잠긴 지역 , 0 : 물에 잠기지 않은 지역
int isVisited[103][103]; // 방문 여부를 저장할 배열
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int board[103][103] : 물의 높이 정보를 저장할 배열이다.

int rain[103][103] : 각 지역이 물에 잠겼는지 여부를 저장할 배열이다. (1 : 물에 잠긴 지역, 0 : 물에 잠기지 않은 지역)

int isVisited[103][103] : BFS 알고리즘에서 방문 여부를 저장할 배열이다.

int dx[4], dy[4] : BFS 알고리즘에서 상하좌우 탐색을 도와줄 변수이다.

 

	int n;
	cin >> n;
	int maxLimit = -1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> board[i][j];
			maxLimit = max(board[i][j], maxLimit);
		}
	}

중첩 for문을 통해 높이 정보를 입력받고, 배열 내의 가장 큰 높이를 maxLimit 변수에 저장한다.

 

int count[maxLimit]; // 모든 높이의 구역의 개수를 저장할 배열
	for(int limit = 0; limit <= maxLimit; limit++) {
		// Init Array
		for(int i = 0; i < n; i++) {
			fill(rain[i], rain[i] + n, 0);
			fill(isVisited[i], isVisited[i] + n, 0);
		}
		
		// Check Area
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(board[i][j] <= limit) rain[i][j] = 1;
			}
		}
 }

int count[maxLimit] : 모든 높이 (0 ~ 9(maxLimit))의 구역의 개수를 저장할 배열이다.

// Init Array Part

fill 함수를 이용해 물에 잠긴 지역 여부를 판별하는 rain 배열과 BFS 알고리즘에서 방문 여부를 판별하는 isVisited 배열을 모두 0으로 초기화한다.

// Check Area Part

for문을 돌면서 limit(현재 높이)보다 작은 지역은 모두 잠긴 지역 (rain[i][j] = 1) 으로 지정한다.

 

		//BFS
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				queue<pair<int,int>> Q;
				// 물에 잠긴 지역이거나, 이미 방문한 지역인 경우 cotinue
				if(rain[i][j] == 1 || isVisited[i][j] == 1) continue;
				Q.push({i, j});
				isVisited[i][j] = 1;
				while(!Q.empty()){
					auto cur = Q.front();
					Q.pop();
					for(int dir = 0; dir < 4; dir++){
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if(rain[nx][ny] == 1 || isVisited[nx][ny] == 1) continue;
						isVisited[nx][ny] = 1;
						Q.push({nx, ny});
					}
				}
				cnt++;
			}

전형적인 BFS 풀이이다.

 

	cout << *max_element(count, count + sizeof(count)/sizeof(int)) << '\n';

마지막으로 max_element 함수를 이용해 count 배열에 저장된 가장 큰 값을 출력한다.

---

#CODE

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[103][103]; // 물의 높이를 저장할 배열
int rain[103][103]; // 1 : 물에 잠긴 지역 , 0 : 물에 잠기지 않은 지역
int isVisited[103][103]; // 방문 여부를 저장할 배열
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int maxLimit = -1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> board[i][j];
			maxLimit = max(board[i][j], maxLimit);
		}
	}
	
	int count[maxLimit]; // 모든 높이의 구역의 개수를 저장할 배열
	for(int limit = 0; limit <= maxLimit; limit++) {
		// Init Array
		for(int i = 0; i < n; i++) {
			fill(rain[i], rain[i] + n, 0);
			fill(isVisited[i], isVisited[i] + n, 0);
		}
		
		// Check Area
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(board[i][j] <= limit) rain[i][j] = 1;
			}
		}

		//BFS
		int cnt = 0;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				queue<pair<int,int>> Q;
				// 물에 잠긴 지역이거나, 이미 방문한 지역인 경우 cotinue
				if(rain[i][j] == 1 || isVisited[i][j] == 1) continue;
				Q.push({i, j});
				isVisited[i][j] = 1;
				while(!Q.empty()){
					auto cur = Q.front();
					Q.pop();
					for(int dir = 0; dir < 4; dir++){
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
						if(rain[nx][ny] == 1 || isVisited[nx][ny] == 1) continue;
						isVisited[nx][ny] = 1;
						Q.push({nx, ny});
					}
				}
				cnt++;
			}
		}
		count[limit] = cnt;
	}

	cout << *max_element(count, count + sizeof(count)/sizeof(int)) << '\n';
}