๋ฐฑ์ค€ 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 ๊ฐ’์„ ๋ฃจํ”„๋งˆ๋‹ค ์ดˆ๊ธฐํ™” ํ•ด์ค˜์•ผ ํ•˜๋Š” ๊ฒƒ์„ ์žŠ์ง€ ๋ง์ž

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ