백준 18808번 - 스티커 붙이기

구현 방법

스티커를 주어진 순서대로 붙이고 회전도 이전 방법이 안될 때 하는 것이라서 순차적으로 접근하는 절차적 방식을 사용한다.(그리디 알고리즘 성격을 갖는다.)

 

이 문제의 핵심은 두 가지로 나눌 수 있다.

1. 스티커의 회전

2. 스티커 붙이기

 

스티커의 회전의 경우는 스티커 객체의 행위로 부여하여 회전 시 새로운 배열을 생성하여 참조를 하게 한다. 스티커의 회전의 경우 직접 해보면서 규칙을 찾고 많이 해보면 규칙이 한 번에 보일 것이다.(중, 고등학교 때 배운 함수의 대칭, 회전을 떠올리면 쉽다.)

 

스티커의 붙이기는 1) 스티커를 붙일 수 있는 지의 여부와 2) 스티커를 붙이는 과정으로 이루어진다.

1) 스티커를 붙일 수 있는 지의 여부는 먼저, 스티커의 길이(행, 열)가 노트를 넘어가는지를 확인하고 둘째, 스티커를 붙일 자리가 노트에 있는지를 확인하는 과정으로 이루어진다.

2) 스티커를 붙이는 과정은 해당 자리의 노트 값을 0으로 하고 결과값(result) 을 증가시킨다.

 

이 문제가 생각보다 복잡해 볼 수 있으나, 친절하게 스티커를 붙이는 순서(왼쪽 위부터, 시계방향으로 회전)가 주어지기 때문에 차근차근 접근하면 쉽게 해결할 수 있다.

코드

package simulation;

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

public class BJ18808 {
    private static int N, M, K;
    private static int[][] map;
    private static Sticker[] stickers;
    private static int result = 0;

    public static void main(String[] args) throws IOException{
        readInput();
        solve();
    }
    
    private static void readInput() 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());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        stickers = new Sticker[K];
    
        for(int i = 0; i < K; i++){
            int row, col;

            st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            col = Integer.parseInt(st.nextToken());

            Sticker sticker = new Sticker(row, col);

            for(int j = 0; j < row; j++){
                st = new StringTokenizer(br.readLine());
                for(int k = 0; k < col; k++){
                    sticker.set(j, k, Integer.parseInt(st.nextToken()));
                }
            }

            stickers[i] = sticker;
        }
    }

    private static void solve(){
        for(Sticker sticker: stickers){
            putSticker(sticker);
        }
        System.out.println(result);
    }

    private static void putSticker(Sticker sticker){
        for(int dir = 0; dir < 4; dir++){
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(canExceedBoundary(sticker, i, j)) continue;
                    if(putStickerOnNotebook(sticker, i, j)) return;
                }
            }
            sticker.rotate();
        }
    }
    private static boolean canExceedBoundary(Sticker sticker, int x, int y){
        return sticker.getColLength() > N - x || sticker.getRowLength() > M - y; 
    }

    private static boolean putStickerOnNotebook(Sticker sticker, int x, int y){
        for(int i = 0; i < sticker.getColLength(); i++){
            for(int j = 0; j < sticker.getRowLength(); j++){
                if(map[x + i][y + j] == 0) continue;
                if(map[x + i][y + j] == 1 && sticker.get(i, j) == 1) return false;
            }
        }
        for(int i = 0; i < sticker.getColLength(); i++){
            for(int j = 0; j < sticker.getRowLength(); j++){
                if(sticker.get(i, j) == 1){
                    map[x + i][y + j] = 1;
                    result++;
                }
            }
        }
        return true;
    }
    
    private static class Sticker{
        private int[][] arr;

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

        public void set(int x, int y, int val){
            arr[x][y] = val;
        }
        
        public int get(int x, int y){
            return this.arr[x][y];
        }

        public void rotate(){
            int colLength = arr.length;
            int rowLength = arr[0].length;

            int[][] temp = new int[rowLength][colLength];

            for(int i = 0; i < rowLength; i++){
                for(int j = 0; j < colLength; j++){
                    temp[i][j] = arr[colLength - 1 - j][i];
                }
            }
            arr = temp;
        }

        public int getColLength(){
            return this.arr.length;
        }

        public int getRowLength(){
            return this.arr[0].length;
        }
    }
}

 

결과