[백준 2468] 안전영역

BFS

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

2468번: 안전 영역

#include <cstdio>
#include <algorithm>
int N;
int city_map[100 + 2][100 + 2];
int visited[100 + 2][100 + 2];
int rain[100 + 2];
int rain_max;


void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &city_map[i][j]);
			if (rain[city_map[i][j]] == 0) rain[city_map[i][j]] = 1;
			if (rain_max < city_map[i][j]) rain_max = city_map[i][j];
		}
	}
}


void DFS(int x, int y, int r)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	visited[x][y] = 1;

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
		if (visited[nx][ny]) continue;
		if (city_map[nx][ny] <= r) continue;
		visited[nx][ny] = 1;
		DFS(nx, ny, r);
	}
}


int get_safe(void)
{
	int cnt = 0;	// r마다 안전영역 개수
	int max_cnt = 1;	// 아무 지역도 물에 잠기지 않을 수 있다. 

	for (int r = 1; r <= rain_max; r++) {	// 비의 높이는 1부터 입력받은 강수량의 최댓값까지만 봐도 됨
		if (rain[r] == 0) continue;
		std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
		cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (city_map[i][j] <= r) continue;
				if (visited[i][j]) continue;
				DFS(i, j, r);
				cnt++;
			}
		}
		//printf("%d %d\n", r, cnt);
		max_cnt = (cnt > max_cnt) ? cnt : max_cnt;
	}
	return max_cnt;
}



int main()
{
	input();
	int ans = get_safe();
	printf("%d\n", ans);
	return 0;
}

나의 논리적 오류를 어떤 이상한 애가 고쳐주었다. 감사 감사 ㅋㅅㅋ

 

 

// input( ) 함수

입력 받는 맵은 지역의 높이 정보이다. 어차피 이 최대 높이를 넘어가면 비가 더 많이와도 잠긴 지역은 동일하므로, 입력 받으면서 지역 높이의 최댓값을 선별해주었다. 그리고 룩업테이블을 만들어 지역 높이를 받아주었다. 이는 이후 get_safe( ) 함수에서 강수량을 인자로 넘겨줄 때 사용할 것이다. 

이 두 과정은 딱히 필요하진 않는데, 루프 돌아가는 횟수 줄이려고 한번 해봤다. 

 

 

// get_safe( ) 함수

 cnt는 강수량 r마다의 안전 영역의 개수를 저장하는 변수이고, max_cnt는 이러한 안전 영역의 최대 개수를 저장하는 변수이다. 이때 max_cnt를 1로 해준 이유는, "비가 오지 않을 경우, 즉 아무 지역도 물에 잠기지 않을 경우"를 고려하기 위함이다. 이 경우를 고려해주었기 때문에 강수량 r을 1부터 탐색해도 되는 것이다. 만약 이 경우를 고려하지 않고 max_cnt의 초기값을 0으로 놓았다면 강수량 r이 0일 때 부터 탐색해야된다. 

 

강수량 r마다 도출될 수 있는 안전영역의 개수를 구해야 하기 때문에 방문 배열과 cnt 변수를 초기화해준다. 또한 해당 지역의 높이가 강수량 보다 작아 잠긴 경우(city_map[i][j] <= r) 무시하고, 해당 지역을 방문한 경우(visited[i][j])도 무시한다. 두 조건에 모두 해당하지 않으면 DFS 함수에 좌표를 인자로 넘겨 인접한 영역 중 물에 잠기지 않은 곳을 탐색한다.

 

DFS 함수가 종료되면 하나의 안전 영역이 만들어진 것이므로 cnt 변수를 올려주고, city_map의 모든 좌표에 대한 탐색이 끝나면 max_cnt(안전 영역의 최대 수)와 cnt(강수량이 r일 때 안전 영역의 수)를 비교하여 더 큰 것을 max_cnt에 저장해준다. 

 

---

++22.10.28 BFS로 다시 풀었다.

수영장 만들기 풀다가 FF 복습하자는 취지로 다시 풀어봤다.

문제 개떡같이 읽고 디버깅한거 실화..? ㅋㅋㅋㅋㅠㅠ 슬프네요...

#include <cstdio>
#include <queue>
#include <algorithm>
int N;
int A[100 + 2][100 + 2];
int max_h;

struct _st
{
	int x, y;
};

std::queue<_st> Q;
int visited[100 + 2][100 + 2];

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
			max_h = (max_h > A[i][j]) ? max_h : A[i][j];
		}
	}
}

void BFS(int x, int y, int rain)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	Q = {};

	Q.push({ x, y });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny]) continue;
			if (A[nx][ny] <= rain) continue;
			Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
}


int get_safe()	// flood-fill
{
	int max_area = 0;
	for (int r = 0; r <= max_h; r++) {	// 비가 아예 안왔을 때부터 max_h까지 왔을 때 
										// 높이 별 탐색
		std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
		int area_cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j]) continue;
				if (A[i][j] > r) {
					BFS(i, j, r);	// 잠기지 않은 영역 구하기 
					area_cnt++;
				}
			}
		}
		max_area = (max_area > area_cnt) ? max_area : area_cnt;
	}
	return max_area;
}



int main()
{
	input();
	int ans = get_safe();
	printf("%d\n", ans);
	return 0;
}