[BOJ/C++]2468(안전 영역)

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

비슷한 문제:1926(그림)
Link: https://www.acmicpc.net/problem/1926

• 2차원 배열의 각 지점에서 탐색해야 하는 문제가 의외로 많이 보이므로 패턴처럼 알아두면 좋을 것 같습니다.
• BFS 및 DFS 코드 둘 다 해봤고, 사실 어느 것을 써도 큰 차이는 없는 문제라 그냥 queue에서 stack으로도 바꿔서 해봤습니다.

1. 물에 잠기지 않는 안전한 영역의 최대 개수를 계산 -> BFS or DFS

정답 코드(BFS)

#include<iostream>
#include<queue>
using namespace std;
#define p pair<int, int>

int n, maxH = 0;
int area[101][101];
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> area[i][j];
			if (maxH < area[i][j]) maxH = area[i][j];
		}
	}
}

void solution() {
	input();
	int answer = 1;
	for (int h = 1; h <= maxH; ++h) {
		int cnt = 0;
		bool vis[101][101]{ 0 };
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (vis[i][j] || area[i][j] <= h) continue;
				queue<p> q;
				q.push(make_pair(i, j));
				++cnt;
				vis[i][j] = 1;
				while (!q.empty()) {
					p cur = q.front(); q.pop();
					for (int dir = 0; dir < 4; ++dir) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
						if (vis[nx][ny] || area[nx][ny] <= h) continue;
						vis[nx][ny] = 1;
						q.push(make_pair(nx, ny));
					}
				}
			}
		}
		if (cnt > answer) answer = cnt;
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

정답 코드(DFS)

#include<iostream>
#include<stack>
using namespace std;
#define p pair<int, int>

int n, maxH = 0;
int area[101][101];
bool height[101];
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> area[i][j];
			if (maxH < area[i][j]) maxH = area[i][j];
		}
	}
}

void solution() {
	input();
	int answer = 1;
	for (int h = 1; h <= maxH; ++h) {
		int cnt = 0;
		bool vis[101][101]{ 0 };
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (vis[i][j] || area[i][j] <= h) continue;
				stack<p> s;
				s.push(make_pair(i, j));
				++cnt;
				vis[i][j] = 1;
				while (!s.empty()) {
					p cur = s.top(); s.pop();
					for (int dir = 0; dir < 4; ++dir) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];
						if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
						if (vis[nx][ny] || area[nx][ny] <= h) continue;
						vis[nx][ny] = 1;
						s.push(make_pair(nx, ny));
					}
				}
			}
		}
		if (cnt > answer) answer = cnt;
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

1.BFS

2.DFS