백준 2468번 : 안전영역 c++

코드

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int map[101][101];
bool visit[101][101];
bool sink[101][101];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1}; 


void dfs(int a, int b){
	visit[a][b] = true;
	int nextx, nexty;
	
	for(int i = 0; i < 4; i++){
		nextx = a + dx[i];
		nexty = b + dy[i];
		
		if(nextx >=0 && nextx < N && nexty >= 0 && nexty < N){
			if(visit[nextx][nexty] == false && sink[nextx][nexty] == false){
				visit[nextx][nexty] = false;
				dfs(nextx, nexty);
			}
		}
	}
}



int main(){
	
	
	cin >> N;
	for(int i = 0; i < 101; i++){
		memset(map[i], 0, sizeof(map[i]));
		memset(visit[i], false, sizeof(visit[i]));
		memset(sink[i], false, sizeof(sink[i]));
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> map[i][j];
		}
	}
	
	int ans[101];
	ans[0] = 1;
	bool chk = false;
	int l = 1;
	while(!chk){

		int a = 0;
		int s = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				visit[i][j] = false;
				if(map[i][j] - 1 >= 0) map[i][j]--;
				else map[i][j] = 0;
			}
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(map[i][j] == 0) sink[i][j] = true;
				if(sink[i][j] == true) s++;
			}
		}
		if(s == N*N) chk = true;
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(sink[i][j] == false && visit[i][j] == false){
					dfs(i, j);
					a++;
				}
			}
		}
		ans[l] = a;
		l++;
	}
	
	int max;
	max = 0;
	for(int i = 0; i < l; i++){
		if( ans[i]> max){
			max = ans[i];	
		}
	}
	
	cout << max;
	
	return 0;
}

해결방법

sink를 정의해서 잠기지 않은곳만 탐색해서 개수를 셉니다.

비가 하나도 안올때도 생각해야해서 ans[0]에는 1을 넣어야 합니다!