백준 1926 번 그림 -자바(Java)

 

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

 

문제

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

입력

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

출력

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

예제 입력 1

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

 

풀이과정

map을 만든뒤 1이면 bfs를 시작한다.

bfs 함수를 실행할때마다 count를 하여 그림의 갯수를 저장

 

bfs에서 길을 찾을때마다 count를 증가해 그림의 넓이를 구한다.

 

처음 제출했을때 실패 했는데

그림이 없을때 0을 하도록 maxArea 초기값을 0으로 해줘야했다.

그전에는 그냥 Integer.MIN_VALUE로 했었다....

 

bfs문제 카테고리에 있어서 bfs 했지만 

dfs로도 풀수 있을거 같다.

 

작성한 코드

import java.awt.*;
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 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int count =0;
        int maxArea = 0;
        int map[][] = new int[n][m];
        boolean checked[][] = new boolean[n][m];
        //주어진 map만듬
        for(int i =0;i < n ;i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            for(int j =0;j<m;j++){
                map[i][j] = Integer.parseInt(st2.nextToken());
            }
        }

        //지나다니면서 count가져옴
        for(int i =0;i < n ;i++){
            for(int j =0;j<m;j++){
                if(map[i][j] == 1 && checked[i][j] == false){
                    int area = bfs(map, checked, i , j);
                    if(area > maxArea){
                        maxArea = area;
                    }
                    count++;
                }
            }
        }
        System.out.println(count);
        System.out.println(maxArea);
    }

    public static int bfs(int[][] map, boolean[][] checked, int x , int y){
        Queue<Point> queue = new LinkedList<>();
        checked[x][y] =true;
        queue.add(new Point(x,y));
        int count = 1;

        int dx[] = {1, -1, 0,0};
        int dy[] = { 0,0, 1, -1};
        while(!queue.isEmpty()){
            Point current = queue.poll();
            for(int i = 0; i< 4;i++){
                int nextX = current.x + dx[i];
                int nextY = current.y + dy[i];

                if(nextX >= 0 && nextX < map.length && nextY >=0 && nextY < map[0].length && map[nextX][nextY] == 1 && checked[nextX][nextY] == false){
                    queue.add(new Point(nextX,nextY));
                    checked[nextX][nextY] = true;
                    count++;
                }

            }

        }

        return count;
    }

}