[백준] 16932번 모양 만들기 -Java

문제 링크

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

문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

알고리즘: BFS

풀이

모양의 최대 크기를 구하는 문제이다.
내가 푼 방식은 먼저 1의 좌표를 모두 list에 넣어줬다. 그리고 one_list를 돌면서 그 1과 모양을 만들 수 있는 인접한 1을 너비 우선 탐색을 진행해 size를 체크했다.
마지막으로 방금 탐색한 모양(인접한 1의 그룹)과 인접한 0의 좌표들에 size를 +해주고, 위 방식을 반복했다.

one_list 반복문이 끝나면 size를 +한 ans 배열에 최댓값을 뽑아내고 그 값에 +1해서 출력하면 모양의 최대 크기를 구할 수 있다.

위 풀이가 가능한 이유는 모양은 서로 변을 공유하고 있기 때문이다. 내가 찾은 모든 모양과 인접한 0의 좌표에(1을 놓을 수 있는) 모든 size를 +해주면 모양의 최대 크기를 만드는 좌표를 쉽게 얻을 수 있다. -> (그 좌표가 0의 좌표중 최댓값을 가지는 좌표) 그리고 1을 아직 놓지 않았기 때문에 마지막에 +1을 해주는 것이다.

소스 코드

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

class Coordinate {
    int x,y;
    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static final int dx[] = {-1, 0, 1, 0};
    static final int dy[] = {0, -1, 0, 1};
    static int N,M;
    static int arr[][];
    static boolean visited[][];
    static ArrayList<Coordinate> one_list = new ArrayList<>();
    static int ans[][];
    static int max_size = -1;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        visited = new boolean[N][M];
        ans = new int[N][M];
        for(int i=0; i<N; i++) {
            StringTokenizer n_st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                arr[i][j] = Integer.parseInt(n_st.nextToken());
                if(arr[i][j]==1) one_list.add(new Coordinate(j,i));
            }
        }
        //탐색
        for(int i=0; i<one_list.size(); i++) {
            Coordinate c = one_list.get(i);
            ArrayList<Coordinate> zero_list = new ArrayList<>();
            if(!visited[c.y][c.x]) {
                make_shape(BFS(c, zero_list), zero_list);
            }
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                max_size = Math.max(max_size, ans[i][j]);
            }
        }
        max_size += 1;
        System.out.println(max_size);
    }
    static int BFS(Coordinate start, ArrayList<Coordinate> zero_list) {
        Queue<Coordinate> que = new LinkedList<>();
        que.add(start);
        visited[start.y][start.x] = true;
        int size = 1;
        while(que.size()!=0) {
            Coordinate c = que.poll();
            for(int i=0; i<4; i++) {
                int nx = c.x + dx[i];
                int ny = c.y + dy[i];
                if((nx>=0 && nx<=M-1) && (ny>=0 && ny<=N-1)) {
                    if(!visited[ny][nx]) {
                        if(arr[ny][nx]==1) {
                            que.add(new Coordinate(nx, ny));
                            visited[ny][nx] = true;
                            size += 1;
                        } else {
                            //0이면
                            zero_list.add(new Coordinate(nx, ny));
                            visited[ny][nx] = true;
                        }
                    } 
                }
            }
        }
        return size;
    }
    static void make_shape(int size, ArrayList<Coordinate> zero_list) {
        for(int i=0; i<zero_list.size(); i++) {
            Coordinate c = zero_list.get(i);
            ans[c.y][c.x] += size;
            visited[c.y][c.x] = false;
        }
    }
}