BOJ 1926 그림 - DFS

 

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

 

- BFS DFS 모두 가능하지만 DFS를 이용하여 풀었다

- 그림의 갯수는 cnt를 이용하여 출력할 수 있지만 가장 큰 그림의 크기를 구하기 위해 ans[502*502]를 선언했다.

- 아직도 DFS가 헷갈려 ㅠㅠ

 

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

int board[502][502];
int visited[502][502];
int n, m; // 1st input
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int ans[502*502]={0};

void dfs(int x, int y, 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<n && nx>=0 && ny<m && ny>=0){
      if(board[nx][ny]==1 && visited[nx][ny]==0){
        dfs(nx, ny, cnt);
      }
    }
  }
}

int main(){
  //입력 처리
  scanf("%d %d", &n, &m);
  for(int i=0; i<n; i++)
    for(int j=0; j<m; j++){
      scanf("%d", &board[i][j]); //2nd input
      visited[i][j]=0; // 방문 배열 초기화.
  }
  int cnt=0;
  //DFS 처리
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(board[i][j]==1 && visited[i][j]==0) {
        dfs(i, j, ++cnt);
      }
    }
  }

  printf("%d\n", cnt); //1st output

  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      ans[visited[i][j]] += 1; //2nd output
    }
  }
  int result = 0;
  for(int i=1; i<502*502; i++){
    result = max(result, ans[i]);
  }
  printf("%d", result);
}