12) 백준 2468 - 안전 영역

2468번: 안전 영역 (acmicpc.net)

2468번: 안전 영역

---

괜히 넘겨짚어서 이런이런...

#include <bits/stdc++.h>

using namespace std;

int pos_x[4] = {0, 1, 0, -1};
int pos_y[4] = {1, 0, -1, 0};

int building[100][100];
int check[100][100];

void dfs(int x, int y, int rain, int N) {
	check[x][y] = 1;
	for(int i = 0; i < 4; i++) {
		int tmp_x = x + pos_x[i];
		int tmp_y = y + pos_y[i];
		if(tmp_x >= 0 && tmp_x < N && tmp_y >= 0 && tmp_y < N &&
		 check[tmp_x][tmp_y] == 0 && building[tmp_x][tmp_y] > rain) {
			dfs(tmp_x, tmp_y, rain, N);
		}
	}
}

int main(void) {
	int N;
	cin >> N;
	
	int highest = 0;
	int lowest = 999;
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> building[i][j];
			if(building[i][j] > highest) {
				highest = building[i][j];
			}
			if(building[i][j] < lowest) {
				lowest = building[i][j];
			}
		}
	}
	
	int answer = 1;
	
	for(int c = lowest; c < highest; c++) {
		int cnt = 0;
		fill(&check[0][0], &check[99][100], 0);
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(check[i][j] == 0 && building[i][j] > c) {
					cnt++;
					dfs(i, j, c, N);
				}
			}
		}
		
		if(answer < cnt) {
			answer = cnt;
		}
	}
	
	cout << answer;
}

DFS 를 사용하였다. BFS로 풀 수 있지만 DFS를 연습하기 위함이랄까!

 

1. 가장 낮은 빌딩 높이와 높은 빌딩 높이를 저장한다.

2. 낮은 빌딩과 높은 빌딩 사이의 값만 비가 온다고 가정하면 된다.

3. DFS 한다!!!

 

나는 빌딩 조건중 가장 낮은 빌딩이 1 일수도 있어서... 그럼 혹시 비온다고 했으니까 비 오는 양도 1부터 시작하나...? 라고 생각한 문제. 하지만 그냥 신경 안써도 된다. 답이 나오는 최소 값은 1...

 

생각보다 잔디 매일 채우는게 쉽지는 않구나..ㅠㅠㅠㅠ

언리얼 공부 기록도 해야하는데.. 엉엉