[백준/Java] 1926번 : 그림

[문제]

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

[조건]

• 시간 제한 : 2초
• 메모리 제한 : 128MB

[입력]

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

[출력]

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

[문제 풀이]

• 방문 배열을 통해 이미 들린 곳인지 확인
• 들린 곳이 아니고, 1이라면(=그림이라면) bfs 수행
• 그림의 개수는 bfs를 수행하기 위해 들어간 수만큼임 (=cnt 변수)
• 가장 넓은 그림은 bfs를 수행하면서 pop될때마다 size++하였고, 이후 max 변수와 비교해 갱신

import java.io.*;
import java.util.*;

class picture{
	int r;
	int c;
	
	picture(int r, int c){
		this.r = r;
		this.c = c;
	}
}

public class boj_1926_그림 {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] arr = new int[N][M];
        boolean[][] check = new boolean[N][M]; 
        for(int r=0; r<N; r++) {
            st = new StringTokenizer(br.readLine());
            for(int c=0; c<M; c++) {
                arr[r][c] = Integer.parseInt(st.nextToken());
            }
        }
        
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        Queue<picture> queue = new LinkedList<>();
        
        int max = 0;
        int cnt = 0;
        for(int r=0; r<N; r++) {
        	for(int c=0; c<M; c++) {
        		if(!check[r][c] && arr[r][c]==1) {
        			cnt++;
        			int size = 0;
        			check[r][c] = true;
        			queue.add(new picture(r, c));
        			while(!queue.isEmpty()) {
        	        	for(int d=0; d<4; d++) {
        	        		int nr = queue.peek().r+dr[d];
        	        		int nc = queue.peek().c+dc[d];
        	        		if(nr>=0 && nr<N && nc>=0 && nc<M && !check[nr][nc] && arr[nr][nc]==1) {
        	        			check[nr][nc] = true;
        	        			queue.add(new picture(nr, nc));
        	        		}
        	        	}
        	        	queue.poll();
        	        	size++;
        	        }
        			max = Math.max(max, size);
        		}
        	}
        }
        
        System.out.println(cnt);
        System.out.println(max);
        
    }
}

 

출처 : 백준 https://www.acmicpc.net/problem/1926