๋ฐฑ์ค 2468
๋ฐฑ์ค 2468 : ์์ ์์ญ
- ๋ฐฐ์ด์ ์ต๋๊ฐ์ ๊ตฌํ๊ณ
- 1์์ ๊ตฌํ ์ต๋๊ฐ๋งํผ dfs๋ฅผ ๋๋ฉด์ ๊ฐ๊ฐ์ ์์ ์ง๋ ๊ฐ์๋ฅผ ๊ตฌํจ
- 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 ๊ฐ์ ๋ฃจํ๋ง๋ค ์ด๊ธฐํ ํด์ค์ผ ํ๋ ๊ฒ์ ์์ง ๋ง์
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(๋ฐฑ์ค 2468), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@msdio/๋ฐฑ์ค-2468์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ
์ธ ๋ฐ๊ฒฌ์ ์ ๋
(Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค