1926번 문제 그림 자바(JAVA) 풀이

문제

https://www.acmicpc.net/problem/1926

1926번: 그림

풀이 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int max;

    private static class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        //입력 부분: start
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] paint = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                paint[i][j] = sc.nextInt();
            }
        }
        //입력 부분: end

        int paintCout = 0; //그림 개수
        max = 0; //그림 크기 최대값
        Queue<Point> queue = new LinkedList<>();
        //BFS로 탐색하기 위해서 배열에서 1인 곳의 좌표를 queue에 담는다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (paint[i][j] == 1) {
                    //BFS의 시작점을 찾았으니 그림의 개수를 1 증가 시킨다.
                    paintCout++; 
                    queue.offer(new Point(i, j));
                    BFS(queue, paint, m, n);
                }
            }
        }
        System.out.println(paintCout);
        System.out.println(max);
    }

    private static void BFS(Queue<Point> queue, int[][] paint, int m, int n) {
        int paintSize = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Point curPoint = queue.poll();
                if (curPoint.x < 0 || curPoint.y < 0 || curPoint.x >= n || curPoint.y >= m) continue;
                if (paint[curPoint.x][curPoint.y] != 1) continue;
                //방문의 표시로 값을 2로 변경한다.
                paint[curPoint.x][curPoint.y] = 2;
                //방문을 했으니 그림의 크기를 1 증가 시킨다.
                paintSize++;
                //상, 하, 좌, 우 방향의 좌표를 queue에 담는다.
                for (int j = 0; j < 4; j++) {
                    queue.offer(new Point(curPoint.x + dx[j], curPoint.y + dy[j]));
                }
            }
        }
        //탐색이 끝났으니 그림 크기를 비교하여 최대값에 넣어준다.
        max = Math.max(max, paintSize);
    }
}