[백준 2468 c++] 안전 영역 V

문제 링크

www.acmicpc.net/problem/2468

2468번: 안전 영역

문제 접근

// 접근: 비의 높이보다 큰 블록만 탐색 -> dfs나 bfs

 

 

 

 

 

 

 

 

 

 

문제 풀이

// 풀이: dfs로 완전탐색하며 안전한 구역의 개수 찾기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

주의

 

// 주의: 비가 오지 않을 경우도 생각해야 해서 안전구역은 항상 1 이상

 

 

 

 

개념

 

// 개념: fill_n(일차원 배열,원소개수 , 채울 값);

 

 

 

 

 

 

 

 

 

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio> // c 문법 헤더파일
#include<string> // c++ 문자열 클래스
#include<vector> // 동적배열 라이브러리
#include<stack>
#include<queue>
#include<algorithm>  // sort와 unique 사용
#include<cmath> // 제곱이나 루트함수 사용
#include<cstring> // memset 함수
#include <set>
#include <map> // map구조체
#include <numeric> //accumulate(v.begin(), v.end(), 0);

// [백준 2468 c++] 안전 영역 V
// 접근: 비의 높이보다 큰 블록만 탐색 -> dfs나 bfs 
// 풀이: dfs로 완전탐색하며 안전한 구역의 개수 찾기
// 주의: 비가 오지 않을 경우도 생각해야 해서 안전구역은 항상 1 이상
// 개념: fill_n(일차원 배열,원소개수 , 채울 값); 
using namespace std; // cin,cout 편하게 사용 라이브러리
#define MAX 101

int n;
int arr[MAX][MAX];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int visited[MAX][MAX];
int maxnum = 1; // 비가아예 안올때 경우1

void dfs(int row, int col,int high)
{
	// 방문표시
	visited[row][col] = 1;

	for (int i = 0; i < 4; i++)
	{
		int currow = row + dy[i];
		int curcol = col + dx[i];
		if (currow < n && curcol < n && currow >=0 && curcol >=0)
		{
			if (visited[currow][curcol] == 0 && arr[currow][curcol] > high)
			{
				//visited[currow][curcol] = 1;
				dfs(currow, curcol, high);
				
			}
		}
	}
}

int main()
{
	// IO 속도 향상
	//ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
		}
	}

	for (int q = 1; q <= 100; q++)
	{
		int c = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (arr[i][j] > q && visited[i][j] == 0) // 방문하지 않았을 때에만
				{ 
					c++;
					dfs(i, j, q);
				}
				
				
			}
		}
		maxnum = max(c, maxnum); // 최대개수 저장
		// 방문배열 초기화
		for(int k=0;k<n;k++)
		{
			fill_n(visited[k],n , 0);
		}
		
	}
	cout << maxnum;

	return 0;
}