[백준/BOJ] 1926번 도화지 (자바/Java)

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

1926번: 그림

---

1. 문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 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

예제 출력 1 

4
9

 

2. 풀이

우리는 지금까지 BFS에서 연결된 것을 저장할 떄, LinkedList를 이용했다. 하지만 이 뿐만 아니라, 2차원 배열을 이용하는 문제 또한 존재했다. 이 문제가 그와 같다.

 

예제와 같은 입력이 주어졌다고 해보자. 우리는 1인 것에만 집중한다.

입력된 이차원 배열에 처음부터 끝까지 순차적으로 움직힌다고 한다면, 반복되면서 이차원 배열에 방문할 때 1인 경우에 집중하면 된다.

 

만약 방문한 값이 1이라면 위, 아래, 왼쪽, 오른쪽을 탐색해서 만약 거기서도 1이라면 쭉쭉 이어지는 방식을 선택했다.

여기서 포인트는 이미 방문한 1은 다시 체크하지 않는다는 것이다. 

 

우리는 방문한 값이 1이라면 사방으로 뻗어나가 다시 탐색하는 과정을 BFS라는 함수를 이용해서 구현했다.

또한 방문한 자리를 체크하기 위해 이중 boolean 배열을 이용하여 확인해주었다.

 

또한 방문한 자리에서 사방을 확인하여 1인 값들을 찾는 find 함수를 구현했다. (이 부분은, BFS 함수에서 따로 체크하는 것 또한 가능하다)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] mn = br.readLine().split(" ");
        int m = Integer.parseInt(mn[0]);
        int n = Integer.parseInt(mn[1]);
        Graph gp = new Graph(m, n);
        for(int i=0; i<m; i++){
            String[] tmp = br.readLine().split(" ");
            for(int j=0; j<n; j++) {
                int x = Integer.parseInt(tmp[j]);
                if(x==1) gp.addEdge(i, j);
            }
        }
        gp.BFS();
        System.out.println(gp.count);
        System.out.println(gp.square);
    }
}
class Graph{
    static int M;
    static int N;
    static int[][] obj;
    int count = 0;
    int square = 0;
    boolean[][] visited;
    Graph(int M, int N){
        this.M = M;
        this.N = N;
        obj = new int[M][N];
        visited = new boolean[M][N];
    }
    void addEdge(int a, int b){obj[a][b] = 1;}

    void BFS(){
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                int s = obj[i][j];
                if(s == 0 || visited[i][j] == true){
                    visited[i][j] = true;
                    continue;
                }
                visited[i][j] = true;
                count++;
                int square_tmp = 1;
                int[] it = find(i, j);
                if(it[0] == 1) square_tmp += BFS(i-1, j);
                if(it[1] == 1) square_tmp += BFS(i+1, j);
                if(it[2] == 1) square_tmp += BFS(i, j-1);
                if(it[3] == 1) square_tmp += BFS(i, j+1);
                if(this.square < square_tmp) square = square_tmp;
            }
        }
    }

    int BFS(int i, int j){
        if(visited[i][j] == true) return 0;
        visited[i][j] = true;
        int square_tmp = 1;
        int[] it = find(i, j);
        if(it[0] == 1) square_tmp += BFS(i-1, j);
        if(it[1] == 1) square_tmp += BFS(i+1, j);
        if(it[2] == 1) square_tmp += BFS(i, j-1);
        if(it[3] == 1) square_tmp += BFS(i, j+1);
        return square_tmp;
    }

    static int[] find(int i, int j){
        int[] res = {0, 0, 0, 0}; // 위 아래 왼 오
        if(i != 0 && obj[i-1][j] == 1) res[0] = 1;
        if(i+1 < M && obj[i+1][j] == 1) res[1] = 1;
        if(j != 0 && obj[i][j-1] == 1) res[2] = 1;
        if(j+1 < N && obj[i][j+1] == 1) res[3] = 1;
        return res;
    }
}

 

3. 결과

 

4. 총평

 - BFS에서 LinkedList 배열을 이용하는 것뿐만이 아니다. 편협하게 생각하지 말자!