[ 백준 18808 ] 스티커 붙이기

 

1. 문제: https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

 

2. 풀이

 

 현재 문제에서 요구하고 있는 것은 노트북의 왼쪽 상단부터 오른쪽 하단으로 진행하며 순차적으로 먼저 주어진 스티커를 붙일 수 있다면 붙이자는 것이다. 이 때, 현재의 스티커 모양으로도 불가능하다면 회전을 시켜서 가능한지 탐색해보아야 한다.

 

 완전탐색으로 풀이해야 할 것 같은데 먼저 이것이 가능한지 알아보자.

모조리 악조건일 경우 노트북은 40x40의 크기, 10x10 스티커가 100개가 있다고 가정했을 때,

 

40 x 40 x 10 x 10 x 100 = 16,000,000의 탐색을 실시해야 하는데 완전탐색으로 풀이하기 적절하다고 판단할 수 있돠.

 

1) 스티커를 붙일 위치를 지정해줄 메소드

2) 위치를 기반으로 스티커를 붙일 수 있는지 판별해줄 메소드

3) 스티커를 회전시켜줄 메소드

 

를 작성하고, 입력받는 스티커를 별도로 저장해두기 보다는 제때제때 판단하고 붙이는 것이 효율적일 것 같다.

또한, 나중에 스티커가 붙은 칸을 순회하기보다는 붙일 수 있을 때 바로 스티커의 면적을 늘려가자!

 

3. 코드

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

public class Main{
	static int N, M;
    static int r, c;
    static int cntSticker;
    static int[][] map;
    static StringTokenizer st;
    
    static boolean isPossible(int y, int x, int[][] sticker){
    	boolean flag = true;
        for(int i = 0; i<r; i++){
        	for(int j = 0; j<c; j++){
            	//붙여야 하는 곳에 이미 스티커가 있다면 false리턴
            	if(sticker[i][j] == 1 && map[y + i][x + j] == 1)
                	return flag = false;
            }
        }
        //붙일 수 있다면 바로 붙여버리자
        if(flag) {
        	for(int i = 0; i<r; i++){
            	for(int j = 0; j<c; j++){
                	if(sticker[i][j] == 1){
                    	cntSticker++; //다시 한 번, 나중에 세아리기 싫으니까 면적 추가
                        map[y + i][x + j] = 1;
                    }
                }
            }
        }
        
        
        return flag;
    }
    
    static int[][] rotate(int[][] sticker){
    	//시계방향 90도 회전
    	int[][] rotated = new int[c][r];
        for(int i = 0; i<c; i++){
        	for(int j = 0; j<r; j++)
            	rotated[i][j] = sticker[r-j-1][i];
        }
        //회전하였기 때문에 r과 c는 반드시 바꿔줘야함
		int tmp = r;
        r = c;
        c = tmp;
        return rotated;
    }
    
    static void setPosition(int dir, int[][] sticker){
    	//네 번 회전을 한다면 원상태이기 때문에 return 처리한다.
    	if(dir == 4) return;
        
        for(int i = 0; i <= N-r; i++){
        	for(int j = 0; j <= M-c; j++){
            	if(isPossible(i, j, sticker))
                	return;
            }
        }
        
        //스티커를 붙이지 못하였기 때문에 회전하고 해당 작업을 반복
        setPosition(dir + 1, rotate(sticker));
    }
    
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        int K = Integer.parseInt(st.nextToken());
        for(int k = 0; k < K; k++){
        	st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            int[][] 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());
            }
            setPosition(0, sticker);
        }
        bw.write(cntSticker + "");
        bw.flush();
        bw.close();
        br.close();
    }
}