[BOJ] 18808. 스티커 붙이기(시뮬레이션).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

단계가 많고 귀찮은..? 시뮬레이션 문제다.

사실은.. 문제에서 주는 단계 그대로 시뮬레이션하면 된다

1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.

2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.

3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.

4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

구현하는게 귀찮고 복잡할 뿐.. 하핳

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    static int N, M, K, R, C, res = 0, scale = 0, notebk[][], sticker[][];
    static int bfr, bfc, nr, nc;
    
    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());    // 놋북 가로
        K = Integer.parseInt(st.nextToken());    // 스티커 개수
        notebk = new int[N][M];
        
        // 스티커를 붙여보자.
        for (int stk = 0; stk < K; stk++) {
            st = new StringTokenizer(br.readLine(), " ");
            R = Integer.parseInt(st.nextToken());    // 행
            C = Integer.parseInt(st.nextToken());    // 열
            sticker = new int[R][C];
            
            scale = 0;
            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());
                    // 스티커 칸
                    if(sticker[i][j] == 1) scale++;
                }
            }
            
            bfr = nr = R;
            bfc = nc = C;
            // 스티커 붙여볼까?
            findLocate();
        }
        
        System.out.println(res);
    }
    
    // 붙일 수 있는 위치 찾아서 붙이기(가장 위쪽, 가장 왼쪽)
    public static void findLocate() {
        // 0, 90, 180, 270도 회전해볼꺼야
        for (int r = 0; r < 4; r++) {
            
            // 붙일 수 있는 위치를 찾다가
            for (int ntr = 0; ntr < N; ntr++) {
                for (int ntc = 0; ntc < M; ntc++) {
                    // 노트북 크기을 벗어나면 pass
                    if(ntr + nr > N || ntc + nc > M) continue;
                    
                    // 다른 스티커와 겹치면 pass
                    boolean isPut = true;
                    out:for (int stkr = 0; stkr < nr; stkr++) {
                        for (int stkc = 0; stkc < nc; stkc++) {
                            // 붙일 수 없는 상황이면
                            if(notebk[ntr+stkr][ntc+stkc] == 1 &&
                                    sticker[stkr][stkc] == 1) {
                                isPut = false;
                                break out;
                            }
                        }
                    }
                    
                    // 이 위치에 붙일 수 있다면 붙이기
                    if(isPut) {
                        for (int stkr = 0; stkr < nr; stkr++) {
                            for (int stkc = 0; stkc < nc; stkc++) {
                                if(sticker[stkr][stkc] == 1) 
                                    notebk[ntr+stkr][ntc+stkc] = 1;
                            }
                        }
                        // 붙였으면 return
                        res += scale;
                        return;
                    }
                }
            }
            // 270도까지 회전시켜도 붙일 곳이 없다면 버리기
            if(r == 3) break;
            // 붙일 자리가 없다면 회전
            rotate90(r);
        }
    }
    
    // 스티커를 붙이지 못했다면 시계방향으로 90도 회전
    public static void rotate90(int th) {
        // 모눈종이도 같이 돌아감
        int tmpSticker[][];
        // 기존 모눈종이, 바뀐 모눈종이
        // 180도 회전은 그대로
        if(th == 1) {
            bfr = nr;
            bfc = nc;
            nr = R;
            nc = C;
            tmpSticker = new int[R][C];
        }
        // 90도, 270도는 행열 바뀜 
        else {
            bfr = nr;
            bfc = nc;
            nr = C;
            nc = R;
            tmpSticker = new int[C][R];
        }
        
        // 기존 열 -> 행
        // 기존 행 ->  열 (N(열)-1-행)
        for (int i = 0; i < bfr; i++) {
            for (int j = 0; j < bfc; j++) {
                tmpSticker[j][nc-1-i] = sticker[i][j];
            }
        }
        
        // 스티커 갱신
        sticker = new int[nr][nc];
        for (int i = 0; i < nr; i++) {
            System.arraycopy(tmpSticker[i], 0, sticker[i], 0, nc);
        }
        
    }
    
}

line 47~89) 스티커를 붙일 수 있는 위치를 찾아서 붙이는 함수

line 52~83) 붙일 수 있는 위치를 찾다가 

line 71~81) 붙일 수 있는 위치를 찾으면 붙인다.

line 87) 붙일 수 있는 곳이 없다면 90도 회전

line 92~127) 스티커를 붙이지 못했을 경우 시계방향으로 스티커를 90도 회전하는 함수

line 93) 90도 회전된 스티커를 저장할 배열이 필요

line 97~111) 스티커의 이전 행/열, 회전된 후의 행/열을 저장

line 115~119) 배열 90도 회전

line 122~125) 회전시킨 배열을 스티커 배열에 복사