Baekjoon 1926 그림 JAVA

1926번: 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

풀이

기본적인 BFS 문제이다.

전체를 찾으면서 하나의 1의 위치에서 연결되어 있는 모든 1들을 탐색한다.

그리고 bfs가 찾는 횟수를 cnt로 저장하고, BFS가 호출되는 횟수를 작품의 갯수로 생각한다

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int max_area,cnt_works, n, m;
	public static void bfs(boolean[][]map, int x, int y) {
		cnt_works++;
		int cnt=1;
		int[] dx = new int[] {0,0,1,-1}, dy = new int[] {1,-1,0,0};
		Queue<Integer> qx = new LinkedList<Integer>(), qy = new LinkedList<Integer>();
		qx.add(x);
		qy.add(y);
		map[x][y]=false;
		while(qx.size()>0) {
			x=qx.poll();
			y=qy.poll();
			for(int i=0;i<4;i++) {
				if(map[x+dx[i]][y+dy[i]])
				{
					map[x+dx[i]][y+dy[i]]=false;
					qx.add(x+dx[i]);
					qy.add(y+dy[i]);
					cnt++;
				}
			}
		}
		if(max_area<cnt)
			max_area=cnt;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		boolean[][]map = new boolean[n+2][m+2];
		for(int i=1;i<=n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=m;j++) {
				if(st.nextToken().equals("1"))
					map[i][j]=true;
			}
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++)
				if(map[i][j])
					bfs(map, i, j);
		}
		System.out.println(cnt_works);
		System.out.println(max_area);
	}
}