[백준] 16932 모양 만들기

www.acmicpc.net/problem/16932

16932번: 모양 만들기

2021-01-03

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main16932 {
    public static int N, M, arr[][], check[][], save[], answer, length;
    public static boolean vtd[];
    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, -1, 0, 1};
    public static Queue<int[]> q;
    public static HashSet<Integer> set;
    
    public static void make(int num) {
        while(!q.isEmpty()) {
            int tmp[] = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            
            for(int i = 0 ;i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                
                if(arr[nx][ny] == 1 && check[nx][ny] == 0){
                    check[nx][ny] = num;
                    q.add(new int[] {nx, ny});
                    save[num]++;
                }
            }
        }
    }
    
    public static void solve(int x, int y) {
        int count = 0;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            
            if(check[nx][ny] > 0 && !set.contains(check[nx][ny])/*!vtd[check[nx][ny]]*/) {
//                vtd[check[nx][ny]] = true;
                set.add(check[nx][ny]);
                count += save[check[nx][ny]];
            }
        }
        if(count > 1) count++;
        if(answer < count) answer = count;
    }
    
//    public static void init() {
//        for(int i = 1; i <= length; i++) vtd[i] = false;
//    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new int[N][M];
        check = new int[N][M];
        save = new int[N*M];
        answer = 0;
        q = new LinkedList<int[]>();
        
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            for(int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int number = 1;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(arr[i][j] == 1 && check[i][j] == 0) {
                    check[i][j] = number;
                    save[number]++;
                    length++;
                    q.add(new int[] {i, j});
                    make(number);
                    number++;
                    length = number;
                }
            } 
        }
        vtd = new boolean[length+1];
        set = new HashSet<>();
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(arr[i][j] == 0) {
//                    init();
                    set.clear();
                    solve(i, j);
                }
            }
        }
        
        System.out.println(answer);
    }
}
 

1/4 HashSet으로 수정

 

#문제풀이

 

재작년에 풀었는데 시간초과가 나서 버려뒀던? 문제이다. 0을 1로 하나씩 바꿔보면서 1의 모양을 만들 수 있는지 체크하는 브루트포스로 풀면 무조건 시간초과가 나는 문제이다.  이번에 다시 시도하려 했는데 딱히 아이디어가 생각 안나서 힌트를 얻었다. 

 

 

(1) 우선 군집화가 필요하다. 아무것도 건드리지 않았을 때, bfs로 군집화를 할 수 있는 부분을 모양들을 번호로 1부터 차례대로 check배열에 지정하였다. 그와 동시에 각각의 군집에 몇 개의 모양을 만들 수 있는지도 save배열에 저장하였다.

(2) 기존의 입력값에서 0인 경우 상하좌우를 돌면서 군집화가 되어 있는 배열을 만날 수 있는지를 체크한다. 만날 수 있다면, (중복되지 않게) 군집이 갖고 있는 개수를 count 해준다. 

 

 

+) 1/4 상하좌우 군집체크 hashset으로 수정 

시간이 약 1/2로 줄어들었다.