[Algorithm] BOJ 18808 스티커 붙이기

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다!

---

18808 스티커 붙이기

---

문제

입력

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 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은 스티커가 붙은 칸을 의미한다.

문제에서 설명한 것과 같이 스티커는 모두 올바른 모눈종이에 인쇄되어 있다. 구체적으로 스티커의 각 칸은 상하좌우로 모두 연결되어 있고, 모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.

출력

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

예제

---

풀이

---

생각

• BaaaaaaaaaaarkingDog님이 개최하신 코딩테스트 대비 모의고사 문제 중 첫 번째 문제.

  • 백준 사이트를 애용하기도 하고, BaaaaaaaarkingDog님 블로그에서 공부도 하고 했던 터라 이번 모의고사를 알게되어 참여하게 되었다.
  • 사실 시간도 없었고, 바로 약속이 잡혀있던 날인터라 급한 마음(?)으로 참여하게 되었는데 역시는 역시 마음이 급하다 보니 자료구조나 알고리즘을 제대로 만들지 못하고 문제를 풀기 시작해서 시간 내에는 못풀었다ㅠㅠ.
  • 약속이 끝난 후에 다시 돌아와서 처음부터 천천히 생각해보고, 다시 작성해서 완료했다.

• 문제가 어렵진 않았으나, 좀 길다보니 긴장이 더 되기도 했다. 첫 단추가 잘못끼워진 게 일단 주어지는 스티커 데이터를 다 저장하려고 했다. 그리고 순회를 돌면서 하나씩 붙여나가면 되겠지 생각했는데, 사실 순서대로 스티커 하나씩 다 완료해나가는거라 하나씩 받고 연산을 수행하면 되던 것이였다.

방법

• 스티커 데이터를 받으면, 스티커를 붙일 수 있는가를 판단한다.
  • 전체 맵(노트북)을 돌면서 스티커의 맨 첫번째 부분이 들어갈 수 있는 부분인가 확인한다.
• 만약 스티커의 맨 첫번째 부분이 들어갈 수 있다면 스티커의 전체 부분이 다 들어갈 수 있는가를 확인한다.
  • 전체 부분이 다 들어갈 수 있다면 스티커를 그 자리에 붙인다. 즉, 노트북에서 스티커를 붙이는 부분에 대해 1로 할당해준다. 그리고 현재 스티커만큼의 사이즈를 결과값에 더해주면서 다음 스티커로 넘어간다.
• 스티커의 맨 첫번째 부분과 들어갈 수 없거나, 스티커의 전체 부분이 들어갈 수 없다면, 다시 전체 맵(노트북)을 순회하며 찾는다.
• 만약 아무 곳도 들어갈 수 없다면, 회전(90도)한다.
  • 다시 위 과정을 반복한다.
• 회전은 최대 3번 (90, 180, 270도) 수행하고, 그럼에도 들어갈 수 없다면 해당 스티커는 버리고 넘어간다.

유의

• 붙일 수 있는가를 확인할 때도 너무 섣불리 판단해서는 안된다. 스티커의 값과 전체 맵(노트북)의 값과 같으면 붙이는게 아니다. 둘다 1(스티커가 붙여져 있음)이 아니면 붙일 수 있는 거다.

  • 스티커가 0, 노트북이 1이면 노트북엔 스티커가 이미 붙어있는데 이번 스티커 공백이 거기에 딱 들어맞게 붙여지는 것
  • 스티커가 1, 노트북이 0이면 노트북엔 공백인데 이번 스티커가 거기에 딱 들어맞게 붙여지는 것
  • 스티커가 0, 노트북이 0이면 둘다 공백이니깐 그냥 공백으로 남게 붙여지는 것
  • 스티커가 1, 노트북이 1이면 둘다 스티커가 있어 들어맞게 붙여지지 못하는 것

• 가장 헷갈리던 것은 회전이다. 좌표관련해서 회전을 시켜본 적이 없어서, 직접 적으면서 점화식을 찾았다.

  • 회전된 값을 바로 할당하면 안된다. 할당되는 위치의 값도 회전되서 새로 할당되야하기 때문. 그래서 임시공간에 저장했다가 다시 할당하는 과정을 수행해야한다.

• 내 코드

  void rotate() {
    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            tmp[y][r - 1 - x] = s[x][y];
        }
    }
    swap(r, c);
    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            s[x][y] = tmp[x][y];
        }
    }
  }

  다 풀고나서 보니 모범답안 코드와 조금 달랐다. 근데 내 코드가 시간이 더 소요 되는 문제가 있었다.

• 모범 답안

  void rotate() {
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            tmp[i][j] = s[i][j];
  
    for (int i = 0; i < c; i++)
        for (int j = 0; j < r; j++)
            s[i][j] = tmp[r - 1 - j][i];
    swap(r, c);
  }

  사실 지금도 왜 이게 더 시간이 적게 걸리는 지 모르겠다. 연산과정을 따져보면 똑같지 않나? 아시는 분 있으시면 알려주십쇼 ㅠㅠ

---

코드

---

#include <iostream>
#include <vector>
#define bb ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int l[41][41], s[11][11], tmp[11][11]; // laptop size, sticker size
int n, m, k;
int r, c;

void rotate() {
    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            tmp[y][r - 1 - x] = s[x][y];
        }
    }
    swap(r, c);
    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            s[x][y] = tmp[x][y];
        }
    }
}

bool glue(int& px, int& py) {
    // check
    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            if (px + x >= n || py + y >= m) return false;
            if (l[px + x][py + y] && s[x][y]) return false;
        }
    }

    // glue
    for (int x = 0; x < r; ++x) {
        for (int y = 0; y < c; ++y) {
            if (s[x][y]) l[px + x][py + y] = 1;
        }
    }
    return true;
}

bool solution() {
    for (int rr = 0; rr < 4; ++rr) {
        for (int a = 0; a < n; ++a) {
            for (int b = 0; b < m; ++b) {
                if (l[a][b] && s[0][0]) continue;
                if (glue(a, b)) return true;
            }
        }
        rotate();
    }
    return false;
}

int main() {
    bb;
    cin >> n >> m >> k;
    int res = 0;
    for (int i = 0; i < k; ++i) {
        cin >> r >> c;
        // sticker input
        int size = 0;
        for (int a = 0; a < r; ++a) {
            for (int b = 0; b < c; ++b) {
                cin >> s[a][b];
                if (s[a][b]) ++size;
            }
        }

        if (solution())
            res += size;
    }
    cout << res << '\n';
    return 0;
}

---

느낀점

• 시험엔 여유로운 마음을 가져야 한다. 너무 급한 마음은 문제를 잘 읽지 못하게 만들고, 어떤 자료구조/알고리즘을 사용할지 헷갈리게 한다.
  • 사실 이런게 다 연습, 문제풀이를 많이하면 해결될 과정들이다. 내가 부족하게 풀어왔고, 부족한 마음으로 임했겠지.
• 미리 슈도코드를 완벽히 작성하고 진입하자. 어느정도 슈도코드를 했다 싶어서 진입하면 작성하지 못한 부분에서 예외가 되는 문제가 꼭 발생한다. 초보니깐 완벽히 작성하고 들어가자.

---

참조

• https://www.acmicpc.net/problem/18808
• https://www.acmicpc.net/contest/view/505
• https://blog.encrypted.gg/938