백준 1926번 그림 JAVA

링크텍스트

설명

map[i][j]==1 && !check[i][j]일때 dfs해서 count를 센다. 그리고 dfs마다 sum++을 해주어 가장 큰 max 값을 구해주었다.
시간복잡도: O(N*M), 공간복잡도: O(N*M)

회독

• PASS

코드

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

public class Main {
        static int n,m;
        static int [][] map;
        static boolean [][] check;
        static int count = 0;
        static int max = 0;
        static int sum = 0;
        static int [] dx = {-1,1,0,0};
        static int [] dy = {0,0,1,-1};
    public static void main(String[] args) throws Exception {
        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];
        check = 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 && !check[i][j]){
                    dfs(i,j);
                    count++;
                    max = Math.max(max,sum);
                    sum = 0;
                }
            }
        }

        System.out.println(count);
        System.out.println(max);
    }

    public static void dfs(int x, int y){
        check[x][y] = true;
        sum++;

        for(int i=0;i<4;i++){
            int xx = x + dx[i];
            int yy = y + dy[i];

            if(xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]==1 && !check[xx][yy]){
                dfs(xx, yy);
            }
        }
    }
}