[백준 / BOJ] 1926 : 그림 (JAVA)

문제

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

 

입력

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

 

출력

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

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

class Main {

    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean[][] v;
    static int[][] arr;
    static LinkedList<Integer[]> queue = new LinkedList<>();
    static int n;
    static int m;


    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        v = new boolean[n][m];

        arr = new int[n][m];

        for (int i = 0; i < n; i++) {
            String[] row = br.readLine().split(" ");

            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(row[j]);
            }
        }

        int cnt = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int k = bfs(i, j);

                if (k > 0) {
                    cnt++;
                    if (max < k) {
                        max = k;
                    }
                }
            }
        }

        System.out.println(cnt);
        System.out.println(max);

    }

    static int bfs(int x, int y) {
        int size = 0;

        if (arr[x][y] != 0 && v[x][y] == false) {
            size++;
            queue.addLast(new Integer[]{x, y});
            v[x][y] = true;
        }

        while (!queue.isEmpty()) {
            Integer[] xy = queue.removeFirst();
            for (int i = 0; i < 4; i++) {
                int nx = xy[0] + dx[i];
                int ny = xy[1] + dy[i];

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

                queue.addLast(new Integer[]{nx, ny});
                v[nx][ny] = true;
                size++;
            }
        }
        return size;
    }
}

 

소견

BFS를 이용한 기본 문제였다. 전체적으로 BFS의 기본 코드를 따라서 작성하였다.

 

문제를 풀면서 예상치 못하게 시간을 많이 소모한 것은 nx, ny의 인덱스 경계값 조건을 설정하는 부분이었다. 처음에는 하나의 조건문 안에 큐에 원소를 넣게 되는 nx, ny의 조건과 arr[nx][ny], v[nx][ny]의 조건을 모두 넣으려고 하였다.

 

하지만 그렇게 하는 것보다, 큐에 원소를 넣지 않는 continue 조건을 설정하는 것이 가시성이 좋다고 보았다. 또한 인덱스(nx, ny)의 조건을 설정한 후에 arr[nx][ny], v[nx][ny]를 조건을 설정하는 것이 exception 발생을 줄일 수 있는 방법이다. nx, ny의 값을 체크하지 않은 채로 arr과 v의 조건을 체크하게 되면 잘못된 인덱스에 접근할 수 있기 때문이다. 

 

그리고 백트래킹의 코드를 보다가 BFS를 구현하려고 하니 패러미터로 오는 x, y의 활용을 헷갈려 시간을 소모했다. nx와 ny를 초기화 하는 부분에서 큐에서 꺼낸 값으로 nx, ny를 초기화해야 하는데, 그냥 x와 y를 이용해 초기화하여 잘못된 계산이 이루어졌다. 백트래킹은 재귀호출을 이용하기 때문에 패러미터로 온 값을 이용해 계산하는 것과 착오한 것이다.

 

BFS, DFS, 백트래킹은 얼추 비슷한 형태의 코드 구성을 가지고 있고, 제대로 이해하지 못하면 풀기 어려우면서도 코딩 테스트에서도 자주 다루는 주제인 만큼 이에 대한 이해를 확실히 해야겠다.