[백준] 1926번 그림 (JAVA)

문제

- 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이 출력

- 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의

- 가로나 세로로 연결된 것은 연결이 된 것

- 대각선으로 연결이 된 것은 떨어진 그림

- 그림의 넓이란 그림에 포함된 1의 개수

 

해결방법

BFS를 활용하여 도화지를 탐색할 수 있도록 하였다. 상, 우, 하, 좌 순서로 각 위치에서 더 뻗어나갈 수 있는 위치를 탐색하였다. 뻗어나가면서 그림의 크기를 구해주었고, 최대 그림의 크기를 비교하면서 update 할 수 있도록 하였다. BFS 코드가 호출될 때는 그림 하나가 그려지는 것이기 때문에 BFS 함수 하단 부분에서 그림의 개수를 update 할 수 있도록 하였다.

 

코드

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

// 그림이 그려진 좌표를 위한 class
class Node {
    int i;
    int j;

    public Node(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

public class Main {
    static int n, m, cnt, maxSize;
    static int[][] image;			// 도화지 배열
    static boolean[][] visited;			// 방문처리 배열

    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());
        image = 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++) {
                image[i][j] = Integer.parseInt(st.nextToken());
            }
        }
		
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
            	// 그림이 그려져있는데 방문하지 않았다면 BFS 탐색 시작
                if(image[i][j] == 1 && !visited[i][j]) {
                    BFS(i, j);
                }
            }
        }
		
        // 그림 개수 출력
        System.out.println(cnt);
        // 그림 중 넓이가 가장 넓은 것의 넓이 출력
        System.out.println(maxSize);
    }
	
    // 그림 탐색
    public static void BFS(int i, int j) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(i, j));
        int count = 0;
        // 상 우 하 좌
        int[] di = {1, 0, -1, 0};
        int[] dj = {0, 1, 0, -1};
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            count++;	// 그림 크기 키우기
            // 네 방향 탐색
            for(int d = 0; d<4; d++) {
                int ni = node.i + di[d];
                int nj = node.j + dj[d];
				
                if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
                if(visited[ni][nj] || image[ni][nj] == 0) continue;
                visited[ni][nj] = true;
                queue.add(new Node(ni, nj));
            }
        }

        cnt++;
        if(count > 1) count--;
        maxSize = Math.max(maxSize, count);
    }
}