[C++] 2468 : 안전 영역

실버 Ⅰ

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, h;
int cnt = 0;
int map[100][100];
int check[100][100] = { 0, };
vector <int> cnts;

void dfs(int a, int b, int water) {

	if (check[a][b] || map[a][b] <= water || a < 0 || a >= n || b < 0 || b >= n) return;

	check[a][b] = 1;

	dfs(a - 1, b, water);
	dfs(a + 1, b, water);
	dfs(a, b - 1, water);
	dfs(a, b + 1, water);
}


int main() {

	scanf("%d", &n);

	int ma = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &h);
			map[i][j] = h;
			if (ma < h) ma = h;
		}
	}

	for (int w = 0; w <= ma; w++) {

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				check[i][j] = 0;
			}
		}
		cnt = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!check[i][j] && map[i][j] > w) {
					dfs(i, j, w);
					cnt++;
				}
			}	
		}
		//printf("수위가 %d 일 때, 영역 개수 : %d\n", w, cnt);

		cnts.push_back(cnt);
	}

	sort(cnts.begin(), cnts.end(), greater<int>());
	printf("%d", cnts.front());
}

 

 

dfs에 인자를 하나 더 생성(수위 : water)

여러 수위에 대하여 dfs를 반복해야 하므로 check를 계속 초기화해줘야 함

근데 처음에 초기화 해줄 때 check[100][100] = {0, } 으로 했더니

전혀 0으로 초기화가 되지 않았다;

 

check[100][100] = {0, }는 말 그대로 초기화 -> initializing 이라서

맨 처음에 값을 넣을 때만 (그러니까 null 값에 값을 넣을 때) 만 되나 보다

 

그래서 그냥 for문 돌면서 값을 일일이 0으로 바꿔줬다

그리고.. 별거 없었음

 

 

+ 중요한 걸 깜박했다..!

 

벡터 내림차순 정렬할 때 cmp 함수를 만들어 주는 방법 말고 이 방법도 있다

sort(cnts.begin(), cnts.end(), greater<int>());

앞으론 이 방법을 사용하자~

 

밑에는 지우가 쓴 낙서

 

 

이명지 빵꾸똥꾸

 

ㅋㅋ