[C++] 안전 영역 - (2468번, BFS)

문제 분류 : BFS

위의 영역에서 1~100 까지 물이 차오르면서 잠기지 않는 안전영역의 갯수를 구하는 문제이다

 

[문제 설명]

 - 기본적인 BFS 문제이다. int 형식의 NxN 배열에서 1~100 범위로 물이 차오를때 잠기지 않는 부분

(위 그림에서의 흰색 부분 - 이어진 부분은 같은 영역으로 처리) 의 개수의 최대값을 구하는 문제이다.

- 물의 높이가 1~100으로 차오르면서 변하는 안전영역의 갯수를 처리해줘야 한다.

 

 

[ISSUE 사항]

- IDE에서는 돌아가는 코드가 백준 사이트에서 돌아가지 않았다. (컴파일 에러)

=> #include <cstring> 코드로 해결

- 입력된 각 좌표의 최대값을 구한후 그 범위까지만 잠긴다고 가정하였는데 틀렸다고 나온다.

=> (수정전) 1~max_water

=> (수정후) 0~101 

 

 

[코드]

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




using namespace std;

struct field {
	int x;
	int y;
};

int N;
int map[101][101];
bool visited[101][101];
int max_water = 0;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int res = 0;
int tmpRes;
queue<field> q;



void rain_bfs(int rain) {
	//이미 q에 좌표 담겨있다.
	//영역 찾으면 계속 q에 추가하니 한 점으로부터 bfs 돌려서 찾기
	while (!q.empty()) {
		field imsi = q.front();
		q.pop();//큐에서 일단 빼주기


		//4방향 탐색
		for (int i = 0; i < 4; i++) {
			
			int nx = imsi.x + dx[i];
			int ny = imsi.y + dy[i];
			
			
			// map 영역 벗어나면 통과
			if (nx<0 || nx>=N || ny<0 || ny>=N) continue;
			
			// 안전영역 이고 방문한적 없으면 q에 넣기
			if (map[nx][ny] > rain && visited[nx][ny] == 0) {
				visited[nx][ny] = true;
				q.push({ nx, ny });
			}
		}
	}
	
}


void Print_map() {
	for (int i = 0; i < N; i++) {
		cout << endl;
		for (int j = 0; j < N; j++) {
			cout << visited[i][j];
		}
	}
}



int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N;

	// 1. 땅 높이 입력받음과 동시에 물의 높이 최대값 구하기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] > max_water) {
				max_water = map[i][j];
			}
		}
	}

	// 2. 1~최대물높이 잠기게 하기
	for (int k = 0; k <= 101; k++) {
		//물 높이마다 visited 배열 초기화 하기
		memset(visited, false, sizeof(visited));
		tmpRes = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] > k && visited[i][j] == 0) {
					field start;
					start.x = i;
					start.y = j;
					q.push(start);
					visited[start.x][start.y] = true;
					rain_bfs(k);

					//빗물 이상 영역 찾고 bfs 돌려서 영역 구했으면
					//tmpRes ++ 해줘서 영역 갯수 구하기
					tmpRes++;

				}
			}
		}
		//각 rain당 영역의 갯수 최댓값 구하기
		res = max(tmpRes, res);
		//Print_map();
		//cout << "res: " << res << endl;
		//cout << "----------------" << endl;
	}
	cout << res << "\n";
	



	return 0;
}