[백준 c++] 2468 안전 영역

문제 설명

https://www.acmicpc.net/problem/2468
어떤 지역에 비가 내렸을 때 물에 잠기지 않는 지역의 최대 개수를 구하는 문제다.
NxN 크기의 2차원 배열 형태로 지역의 높이 정보가 주어진다.높이가 4 이하인 모든 지역이 물에 잠기면 다음과 같으며 안전 영역은 5개가 된다.

아이디어

DFS로 connected component의 최대 개수 구하기

int main()

1. NxN 크기의 2차원 배열 입력받기

{
	int max = 0;
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x;
			a[i][j] = x;
		}
	}

2. int h 는 1씩 높아질 높이다. 높이가 되는 정수의 범위는 1이상 100 이하이지만 아무것도 선택하지 않는 경우도 있기 때문에 0<=h<=100 으로 범위 설정을 했다.

3. 여러번 매 높이마다 dfs를 돌려야하니까 for문 시작에서 visited 배열을 0으로 초기화해주자.

4. 2차원 배열을 DFS하기 위해서 2중 for문을 돌리고
   만약 a[i][j]가 높이 h보다 큰 수라면 안전영역 이라는 뜻이기 때문에 그 때 DFS를 실행해주자.
   높이도 dfs함수에 그대로 가져가기위해 dfs(i, j, h)로 설정했다.
   dfs 함수가 끝나고나서 해당 h이하가 물에 잠겼을때 안전 영역 개수 ret를 ++해줬다.

5. ret이 max인지 비교하고 다음 계산을 위해 ret을 0으로 초기화 해줬다.

	for (int h = 0; h <= 100; h++) {
		fill(&visited[0][0], &visited[0][0] + 101 * 101, 0);
		
        for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] > h && !visited[i][j]) {
					dfs(i, j, h);
					ret++;
				}
			}
		}
		if (ret > max) {
			max = ret;
		}
		ret = 0;
	}

void dfs(int y, int x, int h)

void dfs(int y, int x,int h) {
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= n)continue;
		if (a[ny][nx] > h && !visited[ny][nx]) { //해당 높이보다 높고 방문x
			dfs(ny, nx,h);
		}
	}
	return;
}

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int a[101][101], visited[101][101],x,y,ret;

void dfs(int y, int x,int h) {
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= n)continue;
		if (a[ny][nx] > h && !visited[ny][nx]) {//해당 높이보다 높고 방문x
			dfs(ny, nx,h);
		}
	}
	return;
}

int main()
{
	int max = 0;
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x;
			a[i][j] = x;
		}
	}

	for (int h = 0; h <= 100; h++) {
		fill(&visited[0][0], &visited[0][0] + 101 * 101, 0);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] > h && !visited[i][j]) {
					dfs(i, j, h);
					ret++;
				}
			}
		}
		if (ret > max) {
			max = ret;
		}
		ret = 0;
	}
	cout << max;
}