[BOJ] 백준 1926번 : 그림 - Java

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

 

DFS 풀이

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

public class Main {
    static int n, m;
    
    static int[][] map;
    static boolean[][] visited;
    
    static ArrayList<Integer> result;
    
    static int each = 0;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {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];
        visited = 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());
            }
        }

        result = new ArrayList<Integer>();

        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    each = 0;
                    dfs(i, j);
                    result.add(each);
                }
            }
        }

        if (result.size() > 0) {
            Collections.sort(result);
            System.out.println(result.size());
            System.out.println(result.get(result.size()-1));
        }
        else {
            System.out.println(0);
            System.out.println(0);
        }
    }

    static public void dfs(int y, int x) {
        each ++;
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny>=0 && nx>=0 && ny<n && nx<m) {
                if (map[ny][nx]==1 && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    dfs(ny, nx);
                }
            }
        }
    }
}