[BFS&완전탐색] 백준 2468 안전 영역

www.acmicpc.net/problem/2468

2468번: 안전 영역

수행 시간 : 2시간 + 오류수정시간(약 1시간)

난이도 실버 1의 전형적인 bfs를 통해 해결하는 문제였다. 이 문제에서 가장 큰 고민 부분은 과연 구역을 어떻게 나눌 것 인가 였다. 물에 잠기는 땅은 bfs를 통해 visited를 true로 만들어 주면 되는 것인데 구역을 나눌 방법이 떠오르지 않았다. 그런데 생각을 해본 결과 구역을 나누는 방법은 의외로 간단하다. visited가 false이고 map이 홍수 높이 h 보다 크면 자연스럽게 영역이 되는 것이다.  즉,

			if (!visited[i][j] && map[i][j] >= a) {
				area++;

이 코드를 while(!q.empty()) 들어가기전에 작성해주면 되는 것... 이거 한줄을 고민하기 위해 거의 1시간을 날렸다..ㅜㅜ

 

전체 코드는

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

int n;
int map[101][101];
bool visited[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int h = 0;

int bfs(int a) {
	int area = 0;
	queue<pair<int, int>> q;
	memset(visited, 0, sizeof(visited));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (!visited[i][j] && map[i][j] >= a) {
				area++;
				visited[i][j] = true;
				q.push({ i,j });
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for (int k = 0;k < 4;k++) {
						int nx = dx[k] + x;
						int ny = dy[k] + y;
						if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
							if (visited[nx][ny] == false && map[nx][ny] >= a) {
								visited[nx][ny] = true;
								q.push({ nx,ny });
							}
						}
					}
				}
			}
		}
	}
	return area;
}

int main() {
	int max_size = 0;
	cin >> n;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> map[i][j];
			h = max(h, map[i][j]);
		}
	}
	for (int i = 1;i <= h;i++) {
		int ans = bfs(i);
		if (max_size < ans) {
			max_size = ans;
		}
	}
	cout << max_size;
}