[BOJ] 1926번 그림 자바

문제

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

풀이

#dfs

입력받은 배열을 전체 탐색하면서 방문하지 않았으며 색칠된 경우에 dfs탐색을 진행한다. dfs 함수는 count를 리턴하여 한 구역에 색칠된 개수를 리턴하는데 처음으로 들어가는 값이 있기 때문에 count를 1로 초기화하고 dfs 함수로 진입한다. max함수를 통해 반환값 중 최대값을 구하고 dfs 탐색이 끝나면 area를 증가시켜 구역의 개수를 센다.

dfs함수에서는 배열 값이 0인 경우 함수를 종료시키며 count를 리턴하고 반복문을 돌며 nx, ny위치에 대해 탐색을 진행한다. 방문하지 않았으며 색칠된 경우에 count를 증가시키고 nx,ny에 대해 재귀로 dfs를 호출한다.

 

코드

package BOJ.dfs;

import java.util.*;
import java.io.*;
public class No1926_그림 {
    static int area=0, max=0, count=0;
    static int n,m;
    static int[][] arr;
    static boolean[][] visited;
    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());

        arr=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++){
                arr[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j]&&arr[i][j]==1) {
                    count=1;
                    max=Math.max(max,dfs(i, j));
                    area++;
                }
            }
        }

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

    static int dfs(int x, int y){
        if(arr[x][y]==0) return count;

        visited[x][y]=true;
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];

            if(nx<0||nx>=n||ny<0||ny>=m||visited[nx][ny]) continue;

            if(!visited[nx][ny]&&arr[nx][ny]==1){
                count++;
                dfs(nx,ny);
            }
        }

        return count;
    }
}