백준 Q18808 스티커 붙이기

in Algorithm on baekjoon


문제

https://www.acmicpc.net/problem/18808
혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커의 각 칸은 상하좌우로 모두 연결되어 있다.
또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
혜윤이는 자신의 노트북에 이 스티커들을 붙이기로 했다. 혜윤이의 노트북은 마침 직사각형 모양이고, 스티커가 인쇄된 모눈종이와 같은 간격으로 격자가 그려져 있다. 혜윤이는 스티커들을 먼저 받았던 것부터 차례대로 격자에 맞춰서 붙이려고 한다.
혜윤이가 스티커를 붙이는 방법은 다음과 같다.

  1. 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
  2. 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
  3. 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
  4. 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.

혜윤이는 스티커를 다 붙인 후의 노트북의 모습이 궁금해졌다. 노트북의 크기와 스티커들이 주어졌을 때 스티커들을 차례대로 붙이고 난 후 노트북에서 몇 개의 칸이 채워졌는지 구해보자.

입력

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 ≤ M ≤ 40), 그리고 스티커의 개수 K(1 ≤ K ≤ 100)이 한 칸의 빈칸을 사이에 두고 주어진다.
그 다음 줄부터는 K개의 스티커들에 대한 정보가 주어진다. 각 스티커는 아래와 같은 형식으로 주어진다.
먼저 i번째 스티커가 인쇄된 모눈종이의 행의 개수와 열의 개수를 나타내는 Ri(1 ≤ Ri ≤ 10)와 Ci(1 ≤ Ci ≤ 10)가 한 칸의 빈칸을 사이에 두고 주어진다.
다음 Ri개의 줄에는 각 줄마다 모눈종이의 각 행을 나타내는 Ci개의 정수가 한 개의 빈칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1이다. 0은 스티커가 붙지 않은 칸을, 1은 스티커가 붙은 칸을 의미한다.
문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

출력

첫째 줄에 주어진 스티커들을 차례대로 붙였을 때 노트북에서 스티커가 붙은 칸의 수를 출력한다.

풀이

입력한 세로 X 가로 로 설정된 빈 맵에 주어진 스티커들을 붙여서 채우는 것이 목표이다. 여기서 주어진 규칙을 요약하자면 다음과 같다.

  • 빈 맵의 좌상단 부터 스티커를 붙일 수 있는 지 확인한다.
  • 스티커를 붙일 수 있는 지 확인할 때 스티커 모양대로 붙였을 때 겹치치 않으면 된다.
  • 겹칠 경우, 시계 방향 90도로 회전하여 스티커를 붙일 수 있는지 확인한다.
  • 원본, 90도, 180도, 270도 다 돌아도 붙일 수 없다면, 해당 스티커는 붙일 수 없다고 판단하여 버리고 다음 스티커를 확인한다.
  • 위 과정을 모든 스티커들을 거쳐서 확인한다.

여기서 입력을 받는 건 전체 맵 사이즈와 각 K개의 스티커 정보이다. 그래서 스티커를 붙일 맵 초기화와 K개의 스티커 정보를 넣어주는 공간이 필요하다.

그 다음 요약한 규칙순서대로 구현하자면 먼저 주어진 스티커를 대상으로, 맵의 좌상단 부터 스티커를 붙일 수 있는 구간까지 스티커를 붙일 수 있는 지 확인한다.
스티커를 붙일 수 있는 구간은 0 ~ (전체 맵 가로/세로) - (스티커 구간 가로/세로) + 1 이 된다.
스티커 붙일 수 있는 지는 전체 맵에다가 스티커 공간을 더하여 각 모눈종이가 전부 1이하로만 된다면 겹치지 않는다고 판단하여 불일 수 있다. (0: 빈 공간 / 1: 붙인 공간 / 2~: 겹치는 공간)

// 주어진 스티커 붙이기 시도
private static boolean tryToPutStickerInMap(int[][] sticker){
    int stickerH = sticker.length;
    int stickerW = sticker[0].length;

    // 스티커 붙일 공간 설정 후 확인
    for(int i = 0; i < n - stickerH + 1; i++){
        for(int j = 0; j< m - stickerW + 1; j++){
            if(isValidToPutSticker(i, j, sticker, stickerH, stickerW)){
                putSticker(i, j, sticker, stickerH, stickerW);
                return true;
            }
        }
    }

    return false;
}

// 스티커 붙여도 되는지 확인
private static boolean isValidToPutSticker(int x, int y, int[][] sticker, int stickerH, int stickerW){
    for(int i = x; i < x + stickerH; i++){
        for(int j = y; j < y + stickerW; j++){
            // 2이상인 경우가 겹친 것임
            if(map[i][j] + sticker[i-x][j-y] > 1){
                return false;
            }
        }
    }
    return true;
}

// 스티커 붙이기
private static void putSticker(int x, int y, int[][] sticker, int stickerH, int stickerW){
    for(int i = x; i < x + stickerH; i++){
        for(int j = y; j < y + stickerW; j++){
            map[i][j] += sticker[i-x][j-y];
        }
    }
}

만약 붙일 수 없다면 해당 스티커를 시계방향 90도로 회전을 시켜 확인해봐야 한다. 그게 안된다면 다시 90도를 회전시켜 총 90, 180, 270도 이렇게 총 3번 회전 시킨 것들을 될 때까지 확인하고, 안 되면 다음 스티커로 넘어간다.

X*Y 사이즈의 스티커(A)를 시계방향 90도 회전(B) 하는 방법은 다음과 같다.

  • A의 사이즈 X,Y를 바꾼다. 사이즈를 바꾼 것이 회전하는 B의 사이즈가 된다.
  • B를 B사이즈 맵의 좌상단부터 우하단까지, 좌->우 그리고 상->하로 내용을 넣을 때,
  • A는 A사이즈 맵의 좌하단부터 우상단까지, 하->상 그리고 좌->우로 내용을 넣는다.
  • 이를 수식으로 표현하면 B[i][j] = A[X-1-j][i] 이다.
// 스티커 회전
private static int[][] rotate90(int[][] arr) {
    int n = arr.length;
    int m = arr[0].length;
    int[][] rotate = new int[m][n];

    for (int i = 0; i < rotate.length; i++) {
        for (int j = 0; j < rotate[i].length; j++) {
            rotate[i][j] = arr[n-1-j][i];
        }
    }

    return rotate;
}

...

// 스티커 붙이기 시도
for(int[][] sticker : stickers){
    // 스티커 원본 붙이기 시도
    if(tryToPutStickerInMap(sticker)){
        continue;
    }
    // 90도씩 돌려가며 시도
    for(int i = 0; i < 3; i++){
        sticker = rotate90(sticker);
        if(tryToPutStickerInMap(sticker)){
            break;
        }
    }
}

회전까지 생각하며 모든 스티커들을 확인하여 붙인 다음, 마지막으로 전체 맵에서 붙인 스티커 범위를 세면 끝난다.

결론

이 문제에서 중요한 부분은 첫 번째, 스티커를 집어 넣을 수 있는지 확인하는 것과 두 번째 스티커를 90도 회전하는 것이다. X * Y 의 맵에 A * B의 스티커를 넣을 수 있는지 확인을 하자면 2중 포문 에 2중 포문이라 4중포문이나 될 수 밖에 없다.

그렇다면 X * Y 전체를 살피지 않고, 스티커의 좌측 상단 기준으로 X * Y 중에 스티커를 붙일 수 있는 구간만 살피는 것으로 줄이면 된다. 그러면 (X - A + 1) * (Y - B + 1)이 된다. 그런 다음 A * B 부분을 확인하여 겹침 유무를 판정하게 된다.

두 번째는 회전이다. 이는 도형적으로 그려가면서 이해를 하는 것을 추천드린다. 도형 A에서 90도 회전한 B를 그린 다음 각각의 좌표의 규칙을 찾으면 된다. 회전한 도형 B에서 포문을 좌우상하 방향을 돌때 이전 A는 어디서부터 어떻게 돌게되는지 확인하면 하상좌우 방향으로 도는 것을 착안해서 수식을 세우면 될 것이다.

어찌 보면 이 문제는 수학적으로 도형의 이해가 필요한 문제이다. 즉 공간 감각이 어느정도 갖추면 구현할 수 있는 문제이므로, 코딩하기 전 공간 설계 능력이 반드시 필요하다.