[백준] 1926 그림 - Java

문제 - 그림

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

 

 

입력

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

 

 

출력

 

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

 

 

예제 입력

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

 

예제 출력

4
9

---

접근방법

 

이 문제는 BFS를 이용해서 푸는 문제 이다

모든 그림을 찾아야 하고 그 크기를 알아야하는 문제이다

 

해야할 일은 

상하좌우로 연결된 그림의 크기를 알아내고 도화지에 있는 모든 그림을 찾아야한다

 

다른 BFS 문제처럼 탐색을 하면서 방문 했다는 표시를 남기고 큐를 이용해서 데이터가 만약 1이면 큐에 삽입한다 큐에 원소를 빼면서 상하좌우를 방문하면서 큐가 비어 있을때까지 반복하면 될 것 같다

---

코드 작성

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 {
    static int N;
    static int M;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited;
    static int[][] sketchBook;
    static int count;

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            visited = new boolean[N][M];
            sketchBook = new int[N][M];
            int maxArea = 0;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    sketchBook[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!visited[i][j] && sketchBook[i][j] == 1) {
                        maxArea = Math.max(findArea(i, j), maxArea);
                        count++;
                    }
                }
            }
            System.out.println(count);
            System.out.println(maxArea);


        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public static int findArea(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;
        int area = 1;
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int pollX = poll[0];
            int pollY = poll[1];
            for (int i = 0; i < 4; i++) {
                int ix = pollX + dx[i];
                int iy = pollY + dy[i];
                if (ix >= 0 && ix < N && iy >= 0 && iy < M) {
                    if (!visited[ix][iy] && sketchBook[ix][iy] == 1) {
                        area++;
                        visited[ix][iy] = true;
                        queue.add(new int[] {ix, iy});
                    }
                }
            }
        }
        return area;
    }
}

---

문제 풀고 느낀점

 

• 이 문제는 BFS 개념을 알아야 풀 수 있는 문제이다
• 그리고 BFS를 좀 응용한 문제이다 -> 하지만 비교적 쉬운 문제이다