[백준] 1926 - 그림 자바

문제

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

 

입력

 

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

출력

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

 

예제 입력

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력

4
9

 

풀이 방법

1. 전체 map의 방문 처리를 하는 visited 배열과 queue를 이용, bfs로 풀었다.

2. map을 완전 탐색하며 값이 1이고 visited가 false인 경우에 START!!

   queue에 추가해주고 추가한 queue에 인접한 1과 visited가 false인 좌표를 추가해준다.

3. queue에 추가 할 때마다 넓이를 구하는 변수에 1을 더하고

   queue에 있는 것을 다 계산한 후에 max라는 변수로 넓이 중 가장 넓은 값을 저장한다.

4. 여기까지가 map에서 값이 1이고 visited가 false인 경우에 연결된 넓이를 찾은 것이므로 그림의 개수 +1을 해준다.

 

내 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1926 {
	static int N, M;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M];
		
		for (int y = 0; y < N; y++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int x = 0; x < M; x++) {
				map[y][x] = Integer.parseInt(st.nextToken());
			}
		}
		
		int picCnt = 0;
		int max = 0;
		Queue<Point> queue = new LinkedList<>();
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if(map[y][x] == 0 || visited[y][x]) continue;
				int cnt = 1;
				queue.offer(new Point(x, y));
				visited[y][x] = true;
				while(!queue.isEmpty()) {
					Point cur = queue.poll();
					
					for (int d = 0; d < 4; d++) {
						int ny = cur.y + dy[d];
						int nx = cur.x + dx[d];
						
						if(ny<0 || ny>=N || nx<0 || nx>=M) continue;
						if(map[ny][nx]==0 || visited[ny][nx]) continue;
						
						queue.offer(new Point(nx,ny));
						visited[ny][nx] = true;
						cnt++;
					}
				}
				max = Math.max(max, cnt);
				picCnt++;
			}
		}
		
		System.out.println(picCnt);
		System.out.println(max);

		br.close();

	}
}