[BOJ][Java] 18808. 스티커 붙이기

문제 이해

• n×m 노트북(paper)에 k개의 스티커를 차례대로 붙인다. (우선순위: 왼쪽 위)
• 이미 붙인 칸과 겹치면 안 되며, 한 번 붙이면 고정.
• 모든 위치에 붙일 수 없으면 스티커를 0°, 90°, 180°, 270° 회전하여 시도.
• 최종적으로 스티커가 붙은 칸의 총 개수를 출력.

 

풀이 흐름

1. 탐색

• 현재 스티커를 붙일 수 있는 위치를 왼쪽 위부터 탐색한다.
• (0,0)부터 (n-r, m-c)까지 붙일 수 있는 위치를 순서대로 확인한다.

2. 스티커 붙이기

• 스티커와 종이의 충돌을 검사한다. (둘다 1인 경우)
• 해당 위치에 스티커의 1인 칸과 종이의 1인 칸이 한 번이라도 겹치면 실패 (return false)
• 전부 안 겹치면 종이에 스티커를 붙인다. (붙이는 위치의 paper 값 = 1)

3. 회전

• 위에서 스티커를 못 붙였으면 90° 회전하고 1~2를 다시 수행.
  • 행(r)과 열(c)을 바꾸고 newSticker[i][j] = sticker[c - j - 1][i];
• 붙일 수 있을 때까지 3번 회전한다.
• 4번의 시도를 모두 실패면 이 스티커는 버린다.

4. 스티커 붙인 칸 개수 세기

• 모든 스티커 처리 후 paper가 1인 위치의 개수를 센다.

 

1, 2에서 boolean을 반환하도록 하여, 2를 실패할 시 1을 재시도하고, 1을 실패할 시 3을 수행하도록 한다.

 

코드

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

public class Main {
    static int n, m;
    static int r, c;
    static int[][] paper;
    static int[][] sticker;

    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 k = Integer.parseInt(st.nextToken());
        paper = new int[n][m];

        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            sticker = new int[r][c];

            for (int i = 0; i < r; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < c; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                }
            } // 입력 끝

            for (int i = 0; i < 4; i++) {
                if (search())
                    break;
                rotate();
            }
        }

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

    static boolean search() { // 붙일 공간 탐색
        for (int i = 0; i <= n - r; i++) {
            for (int j = 0; j <= m - c; j++) {
                if (put(i, j))
                    return true;
            }
        }

        return false;
    }

    static boolean put(int startR, int startC) { // 스티커 붙이기
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (sticker[i][j] == 1 && paper[startR + i][startC + j] == 1)
                    return false;
            }
        }

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (sticker[i][j] == 1) {
                    paper[startR + i][startC + j] = 1;
                }
            }
        }
        return true;
    }

    static void rotate() { // 스티커 회전
        r = sticker[0].length;
        c = sticker.length;

        int[][] newSticker = new int[r][c];

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                newSticker[i][j] = sticker[c - j - 1][i];
            }
        }

        sticker = newSticker;
    }

    static int calcSum() {
        int sum = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (paper[i][j] == 1)
                    sum++;
            }
        }

        return sum;
    }

}