티스토리 뷰

알고리즘

[C++] 백준 1926번 그림

J3SUNG 2021. 8. 18. 19:36

DFS, BFS 문제입니다.

그림이 몇개인지 가장 넓이가 큰 그림의 넓이가 몇인지 구하여야 합니다.

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

int map[502][502];
int check[502][502];
int maxCount = 0;
int printCount = 0;

int dfs(int i, int j){
  int count = 0;
  if(map[i][j] == 0){
    return 0;
  } else if(map[i][j] == 1 && !check[i][j]) {
    count = 1;
    check[i][j] = true;
    count += dfs(i+1, j);
    count += dfs(i, j+1);
    count += dfs(i-1, j);
    count += dfs(i, j-1);
  }
  maxCount = max(maxCount, count);
  
  return count;
}

int main(int argc, char *argv[])
{
  int n, m;
  int num;
  
  cin >> n >> m;

  memset(map, 0, sizeof(map));
  memset(check, false, sizeof(check));

  for(int i=1; i<=n; ++i){
    for(int j=1;j<=m; ++j){
      cin >> num;
      map[i][j] = num; 
    }
  }

  for(int i=1; i<=n; ++i){
    for(int j=1;j<=m; ++j){
      if(dfs(i, j) != 0){
        ++printCount;
      }
    }
  }

	cout << printCount << endl;
  cout << maxCount << endl;

  return 0;
}

 

728x90
댓글
댓글쓰기 폼
공지사항