1926_그림

사용 알고리즘: bfs

사용 언어: java

 

import java.awt.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main_bj_1926_그림 {
    static int n, m;
    static int 최고넓이 = 0;
    static int 그림개수 = 0;
    static int[][] paper;
    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        paper = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                paper[i][j] = sc.nextInt();
            }
        }//입력

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //방문처리 2
                if(paper[i][j]==1){
                    그림개수++;
                    paper[i][j] = 2;
                    bfs(i,j,0); //좌표+넓이
                }
            }
        }

        System.out.println(그림개수);
        System.out.println(최고넓이);
    }

    private static void bfs(int x, int y, int sum) {
        Queue<Point> q = new ArrayDeque<>();
        q.offer(new Point(x, y));

        while (!q.isEmpty()){
            Point p = q.poll();
            sum++;

            for (int d = 0; d < 4; d++) {
                int nx = p.x + dx[d];
                int ny = p.y + dy[d];

                if(nx>=0 && nx<n && ny>=0 && ny<m &&
                paper[nx][ny]==1){
                    paper[nx][ny] = 2;
                    q.offer(new Point(nx,ny));
                }
            }
        }

        최고넓이 = Math.max(최고넓이, sum);
    }
}

 

 

알고리즘 선택 이유:

구역 나눠서 구역 개수 세기 + 구역 내에서 인접한 행렬 중 유효값 개수 구하기