백준 2468

3010 단어 algorithmCC

백준 2468 : 안전 영역

  1. 배열의 최대값을 구하고
  2. 1에서 구한 최대값만큼 dfs를 돌면서 각각의 안전지대 개수를 구함
  3. 2의 결과 중 최댓값을 출력

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n;
int a[101][101], visited[101][101];
int m=-1, arr_max=-1;

int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
int ny, nx;

void dfs(int y, int x, int h) {
	visited[y][x]=1;
	for(int i=0; i<4; i++) {
		ny = y+dy[i];
		nx = x+dx[i];
		if(ny<0 || nx<0 || ny>=n || nx>=n) { //배열 벗어나는 경우 
			continue;
		}
		if(!visited[ny][nx] && a[ny][nx]>h) {
			dfs(ny, nx, h);
		}
	}
	
	return;
}

int main() {
	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>>a[i][j];
		}
	}
	
	//먼저 최댓값을 구해야 함
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			if(a[i][j]>arr_max) {
				arr_max = a[i][j];
			}
		}
	}
	
	while(arr_max--) {
		fill(&visited[0][0], &visited[0][0]+101*101, 0);
		int cnt=0;
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(a[i][j]>arr_max && !visited[i][j]) {
					cnt++;
					dfs(i, j, arr_max);
				}
			}
		}
		
		if(cnt>m) {
			m=cnt;
		}
	}
	
	cout<<m<<'\n';
	
	
	return 0;
}

visited 배열과 cnt 값을 루프마다 초기화 해줘야 하는 것을 잊지 말자

좋은 웹페이지 즐겨찾기