백준 2468 안전영역 (bfs) [성공]

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

2468번: 안전 영역

이 문제는 다 풀어놓고 한가지 기준을 생각을 못해 꽤 시간이 걸렸던 문제

 

bfs dfs 둘다 풀이가 가능하다.

 

하지만 나는 bfs로 풀어보겠다.

 

영역을 그리고 다시 탐색하지 않는 과정으로 조금 더 단축시켜 진행하겠다.

#include <iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
vector<vector<int>> list;
vector<vector<int>> list_rain;
queue<pair<int,int>> q;

vector<int> count_list;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int min_ = 10;
int max_ = 0;
int n;
void init_list() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			list_rain[i][j] = 0;
		}
	}
}

void bfs(int depth) {
	while (!q.empty())
	{
		pair<int, int> current = make_pair(q.front().first, q.front().second);
		q.pop();
		int y = current.second;
		int x = current.first;

		for (int w = 0; w < 4; w++) {
			if (x + dx[w] < 0 || y + dy[w] < 0 || y + dy[w] >= n || x + dx[w] >= n) {
				continue;
			}
			else {
				if (list[y + dy[w]][x + dx[w]] > depth&& list_rain[y + dy[w]][x + dx[w]] == 0) {
					q.push(make_pair(x + dx[w], y + dy[w]));
					list_rain[y + dy[w]][x + dx[w]] = 1;
				}

			}
		}


	}
}
void solution() {
	for (int depth = 0; depth <= max_; depth++) {
		int count = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (list[i][j] > depth && list_rain[i][j] == 0) {
					pair<int, int> x_y = make_pair(j, i);
					q.push(x_y);
					list_rain[i][j] = 1;
					count++;
					bfs(depth);
				}
				
			}
		}
		
		init_list();
		count_list.push_back(count);
	}
}




int max_count() {
	int result=0;
	for (int i = 0; i < count_list.size(); i++) {
		if (result <= count_list[i]) {
			result = count_list[i];
		}
	}
	return result;
}
int main() {
	
	cin >> n;
	int temp;
	
	vector<int> temp_int;
	vector<int> temp_list_int;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			temp_int.push_back(temp);
			if (min_ >= temp) {
				min_ = temp;
			}

			if (max_ <= temp) {
				max_ = temp;
			}
			temp_list_int.push_back(0);
		}

		list.push_back(temp_int);
		list_rain.push_back(temp_list_int);
		temp_int.clear();
		temp_list_int.clear();
	}
	solution();

	cout << max_count() << endl;

	return 0;
}

bfs 연습하기에는 정말 좋았던 문제