[백준 16932] 모양 만들기(Java)

문제

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

풀이

BFS를 이용해 풀었다.
먼저, 배열에서 서로 인접하여 모양을 만드는 것들을 그룹화하였다.

1 1 0 0
1 0 1 0
1 0 1 0
0 1 1 0
1 0 0 1

위와 같은 배열을

2 2 0 0
2 0 3 0
2 0 3 0
0 3 3 0
4 0 0 5

위와 같이 그룹화 하였다.
그룹화 하면서 각 그룹마다 모양의 크기(같은 숫자의 개수)를 구하여 저장하였다.

그 후 0 값을 가진 좌표의 크기(1)와,
해당 좌표와 인접한 좌표들이 그룹에 속해있는지 검사하고, 속해있는 경우 해당 그룹의 모양의 크기를 합하였다.
이 연산을 0 값을 가진 좌표들에 대해 반복하였다.

예를 들어서, map[i][j]=0이고 map[i+1][j]=3, map[i][j+1]=2라고 했을 때,

map[i][j]=0 값을 1로 바꿀 때의 모양의 총 크기
= 1+(3 그룹의 모양의 크기)+(2그룹의 모양의 크기)

코드

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

public class Main {

    public static class Shape{
        int y;
        int x;
        public Shape(int y, int x){
            this.y = y;
            this.x = x;
        }
    }
    public static int n;
    public static int m;
    public static final int[][] dists = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    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());

        int[][] map = new int[n][m];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int groupN = 2;
        int[] sumOfGroup = new int[500002];
        Queue<Shape> zeroQ = new LinkedList();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j]==1){
                    makeGroup(map, new Shape(i, j), groupN, sumOfGroup);
                    groupN++;
                }else if(map[i][j]==0) zeroQ.add(new Shape(i, j));
            }
        }
        int solution = 0;
        while(!zeroQ.isEmpty()){
            Shape curShape = zeroQ.poll();
            solution = Math.max(solution, sumOfMerge(map, new Shape(curShape.y, curShape.x), sumOfGroup));
        }
        System.out.println(solution);

    }
    public static int sumOfMerge(int[][] map, Shape startShape, int[] sumOfGroup){
        int i = startShape.y;
        int j = startShape.x;

        int solution = 1;

        HashSet<Integer> set = new HashSet();
        for(int[] dist : dists){
            int nextY = i+dist[0];
            int nextX = j+dist[1];

            if(nextY>=n || nextY<0 || nextX>=m || nextX<0) continue;
            int curGroup = map[nextY][nextX];
            if(curGroup>1 && !set.contains(curGroup)){
                solution += sumOfGroup[curGroup];
                set.add(curGroup);
            }
        }
        return solution;
    }
    public static void makeGroup(int[][] map, Shape startShape, int groupN,
                                 int[] sumOfGroup){
        Queue<Shape> Q = new LinkedList();
        Q.add(startShape);

        int sum = 0;
        while(!Q.isEmpty()){
            Shape curShape = Q.poll();
            int curY = curShape.y;
            int curX = curShape.x;

            if(map[curY][curX]!=1) continue;
            map[curY][curX] = groupN;
            sum++;

            for(int[] dist : dists){
                int nextY = curY+dist[0];
                int nextX = curX+dist[1];

                if(nextY>=n || nextY<0 || nextX>=m || nextX<0) continue;
                if(map[nextY][nextX]==1) {
                    Q.add(new Shape(nextY, nextX));
                }
            }
        }
        sumOfGroup[groupN] = sum;
    }
}```