import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[][] canvas; //그림
static int N, M; //노드 수, 간선 수
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
canvas = new int[N][M];
int max = 0; //최대 크기
int count = 0; //그림 개수
//canvas에 입력받은 그림을 그린다.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++){
if(st.nextToken().equals("1")){
canvas[i][j] = 1;
}
}
}
//그림이 있는 곳(1)에서 DFS 시작
for(int i=0; i<N; i++){
for(int j =0; j<M; j++){
if(canvas[i][j] == 1){
//탐색을 시작한다면 그림이 있는 거니까 개수 증가
count++;
int size = dfs(0, i, j); //DFS로 탐색한 수 = 그림 크기
if(size > max) {
max = size;
}
}
}
}
bw.write(count + "\n" + max);
br.close();
bw.close();
}
static int dfs(int size, int i, int j) {
canvas[i][j] = 0;
size++;
//상하좌우에 대해 탐색
if(i > 0 && canvas[i-1][j] == 1){
size = dfs(size, i-1, j);
}
if(i < N-1 && canvas[i+1][j] == 1) {
size = dfs(size, i+1, j);
}
if(j > 0 && canvas[i][j-1] == 1) {
size = dfs(size, i, j - 1);
}
if(j < M-1 && canvas[i][j+1] == 1) {
size = dfs(size, i, j+1);
}
return size;
}
}
'알고리즘' 카테고리의 다른 글
[백준] 1260 DFS와 BFS - 자바 (0) | 2024.01.18 |
---|---|
[백준] 1012 유기농 배추(DFS) - 자바 (0) | 2024.01.09 |
[백준] 2606 바이러스 (DFS) - 자바 (1) | 2024.01.09 |
[Algorithm] 그리디 알고리즘 (0) | 2023.08.22 |
[Algorithm] 탐색 (0) | 2023.08.21 |