백준 2468 안전 영역

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 n*n 배열에 지역의 높이 정보를 입력받고 비가 n만큼 올때 높이가 n이하인 영역이 잠기게되며 그때 생겨날 수 있는 영역의 개수중 최대 개수를 구하는 문제입니다. 이 문제는 dfs 나 bfs를 이용하여 풀면 되는데 저는 bfs를 이용하여 풀었습니다.

 

낮은 높이부터 시작하여 저는 잠기는 배열의 요소는 그냥 임의적으로 102라는 숫자로 채웠습니다. 그런다음 잠겨진 상태의 배열에서 bfs가 행해지는 횟수가 영역의 개수가 되므로 그 부분을 계속 비교해주며 최대 개수를 구하면 됩니다.

 

다음은 코드입니다. 

 

#include <iostream>
#include <queue>

using namespace std;

int area[101][101];
int visited[101][101];
int nextx[4] = {1,0,-1,0};
int nexty[4] = {0,1,0,-1};
int maxnum; //최대 영역의 개수 
int N; //배열 사이즈 
queue<pair<int, int>> q;

void bfs() {
	while(!q.empty()) {
		
		for(int i = 0; i < 4; i++) {			
			if(q.front().first+nextx[i] < 0 || q.front().first+nextx[i] >= N || q.front().second+nexty[i] < 0 || q.front().second+nexty[i] >= N ) //범위 검사 
				continue;
					
			if(visited[q.front().first+nextx[i]][q.front().second+nexty[i]] == 0 && area[q.front().first+nextx[i]][q.front().second+nexty[i]] != 102) { //방문안하였다면 방문 시킴 
				q.push(make_pair(q.front().first+nextx[i], q.front().second+nexty[i]));
				visited[q.front().first+nextx[i]][q.front().second+nexty[i]] = 1;
			}
		}
		q.pop();
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;
	int maxheight = 0;
	int groupnum = 0;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++) {
			cin >> area[i][j];
			if(maxheight < area[i][j]) //최고 높이를 저장함 
				maxheight = area[i][j];
			}
	
	for(int k = 0; k < maxheight; k++) { //최고 높이까지 탐색 시작 
		for(int i = 0; i < N; i++)
			for(int j = 0; j < N; j++) //k높이 이하의 요소에는 102를 저장(그냥임의적인 숫자) 
				if(area[i][j] <= k)
					area[i][j] = 102;
		
		groupnum = 0;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(area[i][j] != 102 && visited[i][j] == 0) { //방문안한 지점이면 bfs 
					q.push(make_pair(i, j));
					visited[i][j] = 1;
					bfs();
					groupnum++; //bfs를 한 횟수가 그 배열에서의 영역 개수 
				}
			}
		}
		if (maxnum < groupnum)
			maxnum = groupnum;
		
		for(int i = 0; i < 101; i++)
			fill_n(visited[i], 101, 0); //visited 배열 0으로 초기화 
	}
	
	cout<<maxnum;
	return 0;
}