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

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

2468번: 안전 영역

---

---

풀이 : 

 기본적인 dfs 문제지만 주의해야할 조건이 몇개 있어서 버그를 찾는데 애를 먹었다..

접근 방법은 단순하다 앞서 영역의 갯수를 새는 문제는 몇번 풀어봤듯이 젖은 영역을 wet배열에 지정하고 젖은 땅의 경우는 탐색을 하지 않고 젖지 않은 땅중에 방문하지 않은 땅을 dfs로 탐색하면 된다! 그리고 총 호출되는 dfs횟수를 세면 영역의 수를 구할 수 있다! (dfs 내부에서 영역의 최솟값, 최댓값 이런거도 구할 수 있을 듯?) 이때 조심해야 할 것이 있다. 초기 maxCnt의 값을 1로 초기화 해줬는데 젖은 영역이 아무것도 없을 경우, 즉 물에 젖은 땅이 아무것도 없을 경우 전체 영역을 하나의 영역으로 치기 때문에 최소한 1영역 이상이 답이기 때문에다. 

 코드를 살펴보면 입력을 받으면서 영역의 높이 중 최댓값을 찾는다! 영역의 높이는 1~100까지의 정수인데 굳이 1~100까지 다 살펴볼 필요 없이 1부터 최대 높이까지의 경우만 찾으면 된다 이때 실수했던게 최대높이 의 경우 땅이 다 젖으니까 살펴볼필요 없겠지 하고 for문의 조건을 보면 k < heightMax 으로 조건을 잡았는데 처음에 젖은 땅을 설정할 때 높이 보다 작거나 같을 경우(<=)가 아니라 작을경우(<)로 설정을해서 .. 왜틀렸는지 한참을 찾았다.. 허허.. 

 풀이자체는 직관적인데 1~최대 영역 높이까지 반복문을 돌면서 k=1일때 젖은땅 설정(setWet) -> 젖지 않은 땅 중에 방문하지 않은 땅 dfs 탐색 -> 젖지 않았고 방문하지 않은 땅중 상하좌우(dx, dy)조건 확인하면서 탐색 완료 되면 빠져나옴 ->i, j 반복문 다돌면 영역 개수 구해짐 -> 방문, 젖은땅 초기화 => k= 2일때 젖은 땅 설정(setWet) 이런식으로 반복하면 된다

 

코드 : 

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int n;
int map[102][102];
int wet[102][102];
int vis[102][102];
int maxCnt = 1;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

void dfs(int x, int y) {
	vis[x][y] = 1;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
		if (vis[nx][ny] != 0 || wet[nx][ny] == 1) continue;
		dfs(nx, ny);
	}
}

void setWet(int height) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] <= height) {
				wet[i][j] = 1;
			}
		}
	}
}

int main() {
	cin >> n;
	int heightMax = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (heightMax < map[i][j]) {
				heightMax = map[i][j];
			}
		}
	}
	int cnt;
	for (int k = 1; k < heightMax; k++) {
		memset(wet, 0, sizeof(wet));
		memset(vis, 0, sizeof(vis));
		cnt = 0;
		setWet(k);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (vis[i][j] == 0 && wet[i][j] != 1) {
					dfs(i, j);
					cnt++;
				}
			}
		}
		maxCnt = max(maxCnt, cnt);
	}

	cout << maxCnt << endl;

}