[S1] 백준 2468번 안전 영역 C++ 너비 우선 탐색, 플러드 필

리뷰

 

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

비가 내리면 지역이 물에 잠기고 잠기지 않은 영역의 개수가 가장 많은 경우를 구하는 문제

 

 

전역 변수

• n : 정사각형 맵의 한 변의 길이를 저장할 변수
• ans : 정답을 저장할 변수
• v : 방문 처리를 체크하기 위한 논리형 2차 배열
• H : 지역의 값을 저장하기 위한 트리맵
• Pos : 시뮬레이션 시 좌표를 체크하기 위한 구조체, x, y좌표를 정의한다.
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. bfs

void bfs(int sx, int sy, const vector<vector<int>>& temp)

 

플러드 필을 통해 연결된 구역을 잇기 위한 함수

1. 매개변수로 시작 좌표인 sx, sy와 높이 제한 h를 전달 받는다.
2. Pos타입의 큐 q를 초기화 하고, 초기 좌표인 sx, sy를 push해준다.
3. v배열에 sx, sy좌표를 방문표시 해준다.
4. q가 빌 때 까지 while루프를 수행하고 매 루프마다 요소를 한개씩 뽑아준다.
5. 4방향 탐색을 진행하며 맵의 범위 안에 있으며, 맵 상의 값이 h이상이고, 방문하지 않았다면 이동을 진행한다.
6. 이동 후에는 해당 좌표에 방문처리 후 q에 이동한 위치를 push해준다.

 

문제풀이

1. n값을 입력 받고, 맵 정보를 저장할 2차원 정수형 벡터 lst를 n * n크기로 초기화 한다.
2. n * n크기의 맵 정보를 lst배열에 입력 받아주고, 각 지역의 값을 H에 insert해준다.
3. H를 순회하며 각 지역의 높이만큼의 값을 참조해 준다.
4. memset 메서드를 통해 방문 배열을 초기화 해주고, 정수형 변수 cnt를 0으로 초기화 해준다.
5. lst를 순회하며 현재 지역의 값이 h이상이고, 방문하지 않았다면 cnt를 증가시키고 bfs함수를 수행한다.
6. 매 물에 잠기지 않은 지역을 그룹화 해준 뒤 ans와 cnt를 비교해 더 큰 값을 ans에 저장해 준다.
7. 탐색을 마친 후에는 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 아무 지역도 물에 잠기지 않는 경우를 고려해 주지 않았다.
2. set에 0을 추가해 주고 제출하였더니 AC를 받았다.

 

참고 사항

• set에 0을 추가하지 않고 ans의 초기값을 1로 변경해도 AC를 받았다.

 

정답 코드

#include<iostream>
#include<set>
#include<queue>
#include<cstring>
using namespace std;

int n;
int lst[100][100];
bool v[100][100];
set<int> H;
struct Pos {
	int x, y;
};
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void bfs(int sx, int sy, int h) {
	queue<Pos> q;
	q.push({ sx, sy });
	v[sx][sy] = 1;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n && lst[nx][ny] >= h && !v[nx][ny]) {
				v[nx][ny] = 1;
				q.push({ nx, ny });
			}
		}
	}
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> lst[i][j];
			H.insert(lst[i][j]);
		}
	}

	int ans = 1;
	for (int h : H) {
		memset(v, 0, sizeof(v));
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (lst[i][j] >= h && !v[i][j]) {
					cnt++;
					bfs(i, j, h);
				}
			}
		}
		ans = max(ans, cnt);
	}
	cout << ans;
}