백준 16932 (모양 만들기) - java

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

16932번: 모양 만들기

 

문제

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

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

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

 

유형 : BFS 

 

접근 방식

• 1000 * 1000의 크기이기 때문에 모든 경우에 대해 BFS를 수행하면 시간초과이다.
• 해당 문제는 1번의 BFS만으로 결과를 구할 수 있다.
• 우선 애초에 1인 구역의 크기를 미리 구한다. 그리고 해당 구역에 번호를 지정하고 map을 통해 구역의 번호에 대한 크기를 저장한다.
• 그리고 0인 공간에 대해 해당 공간과 4방위로 인접한 구역의 크기의 합과 자신이 변한 크기 (1)을 더한 최댓값을 구한다.
  • 주의해야 할 점은 4방위를 탐색할 때 애초에 계산한 구역을 중복 계산할 수 있기 때문에 set을 사용하도록 한다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static int[][] board;

    static int[][] v;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    static HashMap<Integer,Integer> map = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        StringBuilder sb = new StringBuilder();


        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];
        v = new int[n+1][m+1];

        for(int i=1;i<=n;i++){

            st = new StringTokenizer(bf.readLine(), " ");

            for(int j=1;j<=m;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int num = 1;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(board[i][j] == 1 && v[i][j] == 0){
                    bfs(i,j,num); // 각 구역의 크기를 구한다.
                    num ++;
                }
            }
        }

        int result = 0;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(board[i][j] == 0){
                    HashSet<Integer> set = new HashSet<>();
                    int tmp = 1;

                    for(int k=0;k<4;k++){
                        int nx = i + dx[k];
                        int ny = j + dy[k];

                        if(nx < 1 || nx > n || ny < 1 || ny > m)
                            continue;

                        if(board[nx][ny] == 1 && !set.contains(v[nx][ny])) {
                            set.add(v[nx][ny]); // 이미 계산한 구역은 건너뛰기
                            tmp += map.get(v[nx][ny]); // 구역이 이어질 때 크기 계산
                        }
                    }

                    result = Math.max(result,tmp); // 최댓값 갱신
                }
            }
        }

        System.out.println(result);

        bf.close();
    }

    static void bfs(int x,int y,int num){
        Queue<Node> q = new LinkedList<>();
        v[x][y] = num;
        q.add(new Node(x,y));
        int count = 1;

        while(!q.isEmpty()){
            Node cur = q.poll();

            for(int i=0;i<4;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;

                if(v[nx][ny] != 0 || board[nx][ny] == 0)
                    continue;

                v[nx][ny] = num;
                q.add(new Node(nx,ny));
                count += 1;
            }
        }

        map.put(num,count); // 구역 번호에 대한 크기를 저장한다.
    }

}
class Node{
    int x;
    int y;

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