BOJ 2468 안전 영역 DFS

 

https://www.acmicpc.net/problem/2468

 

 

- BOJ 2667 단지 번호 붙이기와 유사 문제

- DFS로 풀었음

- 사실 처음엔 문제 이해가 되지 않았음. 

높이가 주어지는 것이 아니었고, 모든 높이를 고려했을때 섬(?)이 많은 것을 print 하면 된다.

- 주어진 입력에서 가장 큰 숫자를 저장하여 그 숫자부터 내림차순으로 탐색하였음.

- 높이가 새로 정의 될 때마다 visited 배열 초기화해야한다.

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int map[110][110];
int visited[110][110];
int dx[4]={-1,0,0,1};
int dy[4]={0,-1,1,0};
int n, cnt;
int ans[110*110]={0};

void dfs(int x, int y, int h, int cnt){
  visited[x][y]=cnt;

  for(int i=0; i<4; i++){
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(nx>=0 && nx<n && ny>=0 && ny<n){ //범위안에 있을 떄
      // 방문 안했고,
      if(visited[nx][ny]==0 && (map[nx][ny]>=h)){
        visited[nx][ny]=cnt;
        dfs(nx, ny, h, cnt);
      }
    }
  }
}

int main(){
  scanf("%d", &n);
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      scanf("%d", &map[i][j]);
    }
  }// input end

  int h=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        h = max(h, map[i][j]);
    }
  }

 while(true){
   cnt=0;
   memset(visited, 0, sizeof(visited));

    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
          if(map[i][j]>=h && visited[i][j]==0)
            dfs(i,j, h, ++cnt);
      }
    }
    ans[h]=cnt;
    h--;
    if(h<0) break;
  }

  int cntmax=0;
  for(int i=0; i<110*110; i++){
    cntmax = max(cntmax, ans[i]);
  }
  printf("%d", cntmax);
}