[JAVA] 백준_1926_그림

문제링크

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

1926번: 그림

 

 

 

package BOJ;

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 isVisited[][];
    static int drawingCnt;
    static int largest = 0;
    static int dx[] ={-1,1,0,0};
    static int dy[] = {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];
        isVisited = new boolean[N][M];

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }// 배열 입력

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j] == 1 && !isVisited[i][j]){
                    isVisited[i][j] = true;
                    find(i,j);
                }
            }
        }

        System.out.println(drawingCnt);
        System.out.println(largest);
    }

    private static void find(int i, int j) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(i,j));
        int area = 0;
        drawingCnt++;

        while(!q.isEmpty()){
              Node node = q.poll();
              area++;

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

                  if(nx<0 || ny<0 || nx>=N || ny>=M || isVisited[nx][ny]) continue;
                  if(map[nx][ny] == 1){
                      q.add(new Node(nx,ny));
                      isVisited[nx][ny] = true;
                  }
              }
        }
        largest = Math.max(largest,area);
    }

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