링크

18808 스티커 붙이기

문제

풀이

이 문제는 시물레이션이다.(이해는 빨리했지만 문제푸는데 시간초과날까봐 최적화 + 문제풀이 하느라 헷갈려서 시간이 너무 오래걸렸다)

조건에 맞게 잘 수행하면 된다.

1. 일단 원본 스티커를 우측 상단에서 시작해서 좌측으로 쭉 스캔하고 그 다음에 한칸 내려서 다시 맨 왼쪽에서 오른쪽으로 수행한다.

2. 다 조회 했는데도 없으면 스티커를 시계방향으로 돌려서 다시 1번으로 조회 한다.

이 두개가 핵심 로직이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

//18808
public class Main {
    public static int[][] matrix = null;


    //위 왼쪽부터 시작, 회전은 시계방향
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);
        int k = Integer.parseInt(arr[2]);

        matrix = new int[n][m];

        for(int i=0;i<k;i++){
            arr = br.readLine().split(" ");
            n = Integer.parseInt(arr[0]);
            m = Integer.parseInt(arr[1]);

            int[][] stickerMap = new int[n][m];

			for(int j=0;j<n;j++){
                arr = br.readLine().split(" ");

                for(int l=0;l<arr.length;l++){
                    stickerMap[j][l] = Integer.parseInt(arr[l]);
                }
                
            }

            init(stickerMap);

        }

        int count = 0;

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                if(matrix[i][j] == 1) count++;
            }
        }

        System.out.println(count);

    }

    public static void init(int[][] stickerMap){
        for(int r=0;r<4;r++){

            //위치찾기
            for(int a=0;a<=matrix.length-stickerMap.length;a++){
                for(int b=0;b<=matrix[0].length-stickerMap[0].length;b++){
                    if(findArea(a, b, stickerMap)){
                        return;
                    }
                }
            }

            //로테이트
            stickerMap = rotate(stickerMap);
        
        }
        
    }

    public static boolean findArea(int startX, int startY, int[][] stickerMap){
        int[][] copyMap = new int[matrix.length][matrix[0].length];

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                copyMap[i][j] = matrix[i][j];
            }
        }

        for(int i=startX;i<stickerMap.length + startX;i++){
            for(int j=startY;j<stickerMap[0].length + startY;j++){
                if(stickerMap[i - startX][j - startY] == 1){
                    if(matrix[i][j] != 0) {
                        return false;
                    }
                    copyMap[i][j] = 1;
                }
            }
        }


        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                matrix[i][j] = copyMap[i][j];
            }
        }

        return true;


    }

    //시계방향으로 구현
    public static int[][] rotate(int[][] stickerMap){
        int[][] newMap = new int[stickerMap[0].length][stickerMap.length];

        for(int i=0;i<newMap.length;i++){
            for(int j=0;j<newMap[0].length;j++){
                newMap[i][j] = stickerMap[newMap[0].length - j - 1][i];
            }
        }
        
        return newMap;
    }


}