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

오늘은 백준2468번 안전 영역 문제를 풀어보도록 하자.

BFS, DFS 모두 가능한 문제로 두 가지 방법으로 풀어보았다. 기본적인 BFS, DFS 개념을 습득하기 위해 좋은 문제이다.

문제는 다음과 같다.

                               [접근법]
                               
  공통적인 접근 - 아무 지역도 물에 잠기지 않을 수 있다라는 것을 보고 비가 안 내릴 수도 있다는 것을 캐치해야한다. 그리고
  
  map전체를 1씩 빼면서 기존에 저장되어 있던 값을 최댓값으로 갱신해주어야 한다. 그리고 모든 지역이 0보다 작거나 같으면 볼 필요가
  
  없기 때문에 bool rain()에서 false를 리턴해주고 while문을 빠져나와서 출력해주면 된다.

  1. BFS - 큐를 이용

  2. DFS - 재귀를 이용

                                     [코드]
                                     
                                     ___BFS___
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int map[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool visit[100][100];
int N, answer = 0, cnt = 0;

struct pos {
	int y;
	int x;
};
queue<pos>Q;

bool Inbound(int y, int x) {
	if (y >= 0 && y < N && x >= 0 && x < N) {
		return true;
	}
	return false;
}
bool rain() {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] <= 0) {
				cnt++;
			}
		}
	}
	if (cnt == N * N) {
		return false;
	}
	return true;
}
void cnt_the_safe_area() {
	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;

		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (Inbound(my, mx)) {
				if (map[my][mx] >= 1 && !visit[my][mx]) {
					Q.push({ my, mx });
					visit[my][mx] = true;
				}
			}
		}
	}
	cnt++;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	while (1) {
		if (rain()) {
			cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] >= 1 && !visit[i][j]) {
						Q.push({ i,j });
						cnt_the_safe_area();
					}
				}
			}
			answer = max(answer, cnt);
		}
		else {
			break;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visit[i][j] = false;
				map[i][j]--;
			}
		}
	}
	cout << answer << '\n';
}


                                     ___DFS___
#include <iostream>
#include <algorithm>
using namespace std;

int map[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
bool visit[100][100];
int N, answer = 0, cnt = 0;

bool Inbound(int y, int x) {
	if (y >= 0 && y < N && x >= 0 && x < N) {
		return true;
	}
	return false;
}
bool rain() {
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] <= 0) {
				cnt++;
			}
		}
	}
	if (cnt == N * N) {
		return false;
	}
	return true;
}
void cnt_the_safe_area(int y, int x) {
	visit[y][x] = true;

	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (Inbound(my, mx)) {
			if (map[my][mx] >= 1 && !visit[my][mx]) {
				cnt_the_safe_area(my, mx);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	while (1) {
		if (rain()) {
			cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] >= 1 && !visit[i][j]) {
						cnt_the_safe_area(i,j);
						cnt++;
					}
				}
			}
			answer = max(answer, cnt);
		}
		else {
			break;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visit[i][j] = false;
				map[i][j]--;
			}
		}
	}
	cout << answer << '\n';
}