🗒️ 문제
https://www.acmicpc.net/problem/18808
❓설명
스티커를 겹치지 않고 붙였을 때, 스티커가 모눈종이를 차지하는 칸의 수를 출력하라!
[스티커 붙이는 법 💖]
- 스티커는 순차적으로 붙인다.
- 스티커를 회전시키지 않고 모눈종이에서 떼어낸다.
- 다른 스티커와 겹치거나 노트북을 벗어나지 않으면서 스티커를 붙일 수 있는 위치를 찾는다. 혜윤이는 노트북의 위쪽부터 스티커를 채워 나가려고 해서, 스티커를 붙일 수 있는 위치가 여러 곳 있다면 가장 위쪽의 위치를 선택한다. 가장 위쪽에 해당하는 위치도 여러 곳이 있다면 그중에서 가장 왼쪽의 위치를 선택한다.
- 선택한 위치에 스티커를 붙인다. 만약 스티커를 붙일 수 있는 위치가 전혀 없어서 스티커를 붙이지 못했다면, 스티커를 시계 방향으로 90도 회전한 뒤 2번 과정을 반복한다.
- 위의 과정을 네 번 반복해서 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
조건 ❗
모눈종이 크기 (N x M)
- N(1 ≤ N ≤ 40)
- M(1 ≤ M ≤ 40)
스티커
- 개수 K(1 ≤ K ≤ 100)
- 스티커의 크기 (R x C)
- Ri(1 ≤ Ri ≤ 10)
- Ci(1 ≤ Ci ≤ 10)
모눈종이의 크기는 스티커의 크기에 꼭 맞아서 상하좌우에 스티커에 전혀 포함되지 않는 불필요한 행이나 열이 존재하지 않는다.
💡 발상
시키는대로 동작을 나누면 아래와 같다. 크게 이런 동작이 필요하구나를 함수로 만들고 시작했다.
for(int t=0; t<K; ++t) // 스티커를 순차적으로 붙인다.
{
for(int d=0; d<4; ++d)
{
if(attach(t, d))// t번째 스티커를 d방향으로 붙일겁니다.
break; // 붙이는 것에 성공하면 다음 스티커를 붙이자
rotation90(t); // 안되면 90도 회전
}
}
1. `rotation90(t)` - 사실상 가장 어려움
현재 스티커를 시계방향으로 90도 돌려주는 함수로 스티커를 순차적으로 붙이므로 다시 재사용하지 않기에 돌린 값을 덮어썼다.
원래 위치를 기준으로 새로운 배열의 어느 위치에 넣으면 좋을까로 생각했습니다.
void rotation90(Sticker& target)
{
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
tmp_sticker[j][**target.r - i - 1**] = target.grid**[i][j]**;
}
}
// 전역에 선언되어 있는 sticker에 deep copy
std::swap(target.r, target.c);
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
target.grid[i][j] = tmp_sticker[i][j];
}
}
}
2. `attach()`
bool attach(Sticker& target)
{
for(int i=0; i<N; ++i)
{
for(int j=0; j<M; ++j)
{
// 스티커가 모눈종이의 사이즈를 넘어가지 않도록 크기 확인 및 가지치기
if(!isValid(i + target.r - 1, j + target.c -1))
break;
// 여길 시작점으로 붙일 수 있는지 2중포문으로 확인
if(try_attach(make_pair(i, j), target))
{
// 붙일 수 있다면 붙이고 사이즈도 갱신하고 붙였다고 true 반환
painting(make_pair(i, j), target);
answer += target.size;
return true;
}
}
}
return false; // 못 붙였다고 결과를 줘서 회전해야할지 판단할 때 사용
}
2-1.`try_attach()` : 우선순위에 따라 붙일 위치를 탐색한다.
- 가능한. 가장 위쪽
- 가장 위쪽이 여러개라면 가장 왼쪽
2중 포문을 이용하면 가장 간단하게 볼 수 있다. 시간이 꽤 큰것 같지만 이정도는 괜찮고 (?) 문제에서 시간을 2초나 주어서 진행했다.
🤔 시간 복잡도 : O(10^6)
모든 모눈 종이 위치에서 탐색 O(NxN)스티커의 최대 크기 O(KxK)
= O(100x100) x O(100 x 100) = O(10^6)
2-2. `painting()` : 모눈 종이에 스티커 붙이기
void painting(const pii& start, const Sticker& target)
{
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
if(target.grid[i][j]) // 스티커가 있는 부분만 표기
grid[i + start.first][j + start.second] = 1;
}
}
}
한 장소에 여러 스티커를 붙일 순 없으니까 스티커 붙였다고 전역변수 grid에 꼭꼭 표시해준다.
🖥️ 구현
전역변수
constexpr int MAX_N = 40 + 1; // 모눈종이의 최대 크기
constexpr int MAX_M = 10 + 1; // 스티커의 최대 크기
int N, M, K, answer = 0;
int grid[MAX_N][MAX_N] = {false, }; // 모눈종이
int tmp_sticker[MAX_M][MAX_M] = {false, }; // 스티커를 회전시킨 결과를 담는 변수
// 회전시킬 때마다 생성할 필요가 없기 때문에 그냥 전역으로 선언하여 사용해주었다.
struct Sticker
{
int r, c, size = 0; // 미리 차지하는 칸을 계산해 주었다.
int grid[MAX_M][MAX_M] = {0, };
} stickers[100];
solution 함수
for(auto& target : stickers)
{
for(int d=0; d<4; ++d)
{
if(attach(target))// t번째 스티커를 d방향으로 붙이려고 합니다
break;
if(d == 3) break;
rotation90(target); // 안되면 돌려 - 한번 붙이고 말거라 그냥 덮어씀
}
}
✏️ 전체 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
typedef pair<int, int> pii;
constexpr int MAX_N = 40 + 1;
constexpr int MAX_M = 10 + 1;
int N, M, K, answer = 0;
int grid[MAX_N][MAX_N] = {false, };
int tmp_sticker[MAX_M][MAX_M] = {false, };
struct Sticker
{
int r, c;
int size = 0;
int grid[MAX_M][MAX_M] = {0, };
} stickers[100];
bool isValid(const int x, const int y)
{
if(x<0 || y<0 || x>=N || y>=M)
return false;
return true;
}
bool try_attach(const pii& start, const Sticker& target)
{
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
if(grid[i + start.first][j + start.second] && target.grid[i][j])
return false;
}
}
return true;
}
void painting(const pii& start, const Sticker& target)
{
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
if(target.grid[i][j])
grid[i + start.first][j + start.second] = 1;
}
}
}
bool attach(Sticker& target)
{
for(int i=0; i<N; ++i)
{
for(int j=0; j<M; ++j)
{
if(!isValid(i + target.r - 1, j + target.c -1))
break;
if(try_attach(make_pair(i, j), target))
{
painting(make_pair(i, j), target);
answer += target.size;
return true;
}
}
}
return false;
}
void rotation90(Sticker& target)
{
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
tmp_sticker[j][target.r - i - 1] = target.grid[i][j];
}
}
std::swap(target.r, target.c);
for(int i=0; i<target.r; ++i)
{
for(int j=0; j<target.c; ++j)
{
target.grid[i][j] = tmp_sticker[i][j];
}
}
}
void solve()
{
for(auto& target : stickers)
{
for(int d=0; d<4; ++d)
{
if(attach(target)
break;
if(d == 3) break;
rotation90(target);
}
}
}
int main()
{
int r, c;
cin >> N >> M >> K;
for(int i=0; i<K; ++i)
{
cin >> r >> c;
stickers[i].r = r;
stickers[i].c = c;
for(int j=0; j<r; ++j)
{
for(int k=0; k<c; ++k)
{
cin >> stickers[i].grid[j][k];
if(stickers[i].grid[j][k])
stickers[i].size++;
}
}
}
solve();
cout << answer;
return 0;
}
💡 만약 최적화를 한다면?
시간초과가 난다면 아래와 같이 해야겠다 생각을 했습니다.
똑같이 생긴 스티커가 있을 수도 있으니까 회전 시간 아끼기
map<스티커모양, 스티커[3]>
- 한번도 돌린 적 없다면 돌리고 여기에 저장하고
- 돌린 적있으면 바로 빼서 사용해서 rotation90 중복 줄이기
스티커모양을 string으로 저장하기
010
011 => 010_011_111
111