[BaekJoon] 18808 스티커 붙이기 (Java)

1.  문제 링크

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

2.  문제

요약

• 혜윤이는 노트북에 붙일 수 있는 스티커들을 받았는데, 스티커는 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있습니다.
• 모눈종이의 크기는 스티커의 크기에 꼭 맞아, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않습니다.
• 혜윤이는 자신의 노트북에 스티커들을 붙이기로 하였는데, 노트북은 직사각형 모양이고 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있습니다.
• 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰 붙이려고 하는데, 다음과 같은 방법으로 붙이려고 합니다.
  1. 스티커를 회전시키지 않고 모눈종이에서 떼어냅니다.
  2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾습니다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택합니다. 가장 위쪽에 해당하는 위치도 여러 곳이라면 그 중 가장 왼쪽의 위치를 선택합니다.
  3. 선택한 위치에 스티커를 붙입니다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복합니다.
  4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버립니다.
• 노트북의 크기와 스티커들이 주어졌을 때, 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 40보다 작거나 같은 노트북의 세로 길이 N과 가로 길이 M, 1보다 크거나 같고 100보다 작거나 같은 스티커의 개수 K가 주어지고 두 번째 줄부터 K개의 줄에 스티커들에 대한 정보가 주어집니다. 각 스티커는 다음과 같은 형식으로 주어집니다. i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 $R_i, C_i$가 주어지고 다음 $R_i$개의 줄에 각 줄마다 모눈종이의 각 행을 나타내는 $C_i$개의 정수가 주어집니다. 각 칸에 들어가는 값은 0, 1인데, 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미합니다.
  • 1 <= $R_i$, $C_i$ <= 10
  • 스티커는 모두 올바른 모눈종이에 인쇄되어 있습니다.
  • 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않습니다.
• 출력: 첫 번째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M, K;
    static boolean[][] isAttached;
    static Sticker[] stickers;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt(); // 세로 길이
        M = scanner.nextInt(); // 가로 길이
        K = scanner.nextInt(); // 스티커 개수
        isAttached = new boolean[N][M];
        stickers = new Sticker[K];

        for(int idx = 0; idx < K; idx++) {
            int row = scanner.nextInt(), col = scanner.nextInt();
            stickers[idx] = new Sticker(row, col);

            for(int x = 0; x < row; x++) {
                for(int y = 0; y < col; y++) {
                    int num = scanner.nextInt();
                    if(num == 1) stickers[idx].attached[x][y] = true;
                }
            }
        }
    }

    static void solution() {
        for(int idx = 0; idx < K; idx++)
            attachSticker(stickers[idx]);

        System.out.println(getAttachedNum());
    }

    static int getAttachedNum() {
        int count = 0;

        for(int row = 0; row < isAttached.length; row++) {
            for(int col = 0; col < isAttached[row].length; col++) {
                if(isAttached[row][col]) count++;
            }
        }

        return count;
    }

    static void attachSticker(Sticker sticker) {
        if(isPossible(sticker.attached)) return;
        if(isPossible(sticker.rotate90())) return;
        if(isPossible(sticker.rotate180())) return;
        isPossible(sticker.rotate270());
    }

    static boolean isPossible(boolean[][] attached) {
        int rowNum = attached.length, colNum = attached[0].length;

        if(rowNum > isAttached.length || colNum > isAttached[0].length) return false;

        for(int x = 0; x <= isAttached.length - rowNum; x++) {
            for(int y = 0; y <= isAttached[0].length - colNum; y++) {
                boolean flag = true;
                Loop :
                for(int row = x; row < x + rowNum; row++) {
                   for(int col = y; col < y + colNum; col++) {
                       if(isAttached[row][col] && attached[row - x][col - y]) {
                           flag = false;
                           break Loop;
                       }
                   }
               }

                if(flag) {
                    for(int row = x; row < x + rowNum; row++) {
                        for(int col = y; col < y + colNum; col++)
                            if(attached[row - x][col - y]) isAttached[row][col] = true;
                    }
                    return true;
                }
            }
        }

        return false;
    }

    static class Sticker {
        boolean[][] attached;

        public Sticker(int row, int col) {
           attached = new boolean[row][col];
        }

        public boolean[][] rotate90() {
            boolean[][] rotate = new boolean[attached[0].length][attached.length];

            for(int row = 0; row < attached.length; row++) {
                for(int col = 0; col < attached[row].length; col++)
                    rotate[col][(attached.length - 1) - row] = attached[row][col];
            }

            return rotate;
        }

        public boolean[][] rotate180() {
            boolean[][] rotate = new boolean[attached.length][attached[0].length];

            for(int row = 0; row < attached.length; row++) {
                for(int col = 0; col < attached[row].length; col++)
                    rotate[(attached.length - 1) - row][(attached[row].length - 1) - col] = attached[row][col];
            }

            return rotate;
        }

        public boolean[][] rotate270() {
            boolean[][] rotate = new boolean[attached[0].length][attached.length];

            for(int row = 0; row < attached.length; row++) {
                for(int col = 0; col < attached[row].length; col++)
                    rotate[(attached[row].length - 1) - col][row] = attached[row][col];
            }

            return rotate;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}