[백준 2468] 안전 영역

문제링크 : https://www.acmicpc.net/problem/2468

💻 문제 풀이 : C++

#include <iostream>
#include <cstring>
#include <queue>

#define MAP_SIZE 105

using namespace std;

int N;
int MAP[MAP_SIZE][MAP_SIZE];
int visited[MAP_SIZE][MAP_SIZE];
int safe[MAP_SIZE][MAP_SIZE];
int dr[4] = { 0, 0, -1, 1 };
int dc[4] = { -1, 1, 0, 0 };

struct Coord {
	int row;
	int col;
};

int my_max(int a, int b)
{
	return a > b ? a : b;
}

void bfs(Coord start, int height)
{
	queue<Coord> nowQ;
	nowQ.push(start);
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			int next_row = now.row + dr[i];
			int next_col = now.col + dc[i];
			if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N) continue;
			if (MAP[next_row][next_col] > height) continue;
			if (visited[next_row][next_col] != 0) continue;
			visited[next_row][next_col] = 1;
			nowQ.push({ next_row, next_col });
		}
	}
}

void safe_bfs(Coord start) 
{
	queue<Coord> nowQ;
	nowQ.push(start);
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			int next_row = now.row + dr[i];
			int next_col = now.col + dc[i];
			if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N) continue;
			if (visited[next_row][next_col] == 1) continue;
			if (safe[next_row][next_col] == 1) continue;
			safe[next_row][next_col] = 1;
			nowQ.push({ next_row, next_col });
		}
	}
}

int main()
{
	cin >> N;

	int answer = 0;
	int max_height = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> MAP[i][j];
			if (max_height < MAP[i][j])	
				max_height = MAP[i][j];
		}
	}
    // !? 문제 이상함 ?!
	// MAX 기준 탐색 (0 ~ 100)
	for (int i = 0; i <= max_height; i++)
	{
		int now_answer = 0;
		memset(visited, 0, sizeof(visited));
		memset(safe, 0, sizeof(safe));
		// 물에 잠기게 하기!
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < N; k++)
			{
				if (MAP[j][k] <= i && visited[j][k] == 0)
				{
					visited[j][k] = 1;
					bfs({ j, k }, i);
				}
			}
		}
		// 안전한 영역 탐색
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < N; k++)
			{
				if (visited[j][k] == 0 && safe[j][k] != 1)
				{
					now_answer += 1;
					safe[j][k] = 1;
					safe_bfs({ j, k });
				}
			}
		}
		answer = my_max(answer, now_answer);
	}
	

	// 최대 개수

	int debug = 0;
	cout << answer << endl;

	return 0;
}

---

📌 memo 😊

---

ref)