[구현]백준18808번 스티커 붙이기
업데이트:
백준18808
배울 것이 많은 문제였다. 문제를 해결하는 방법 자체는 크게 어렵지 않았다. 문제에서 요구하는 것을 차례로 알아보면 다음과 같다.
- 스티커의 저장
- 스티커 부착 가능 여부 확인
- 스티커의 회전
문제가 길고 구현할 것이 많기 때문에 헷갈리지 않도록 각 기능을 함수로 구현하면 좋다.
1. 스티커의 저장
스티커는 구조체를 이용해 구현하였다.
구조체는 다음과 같은 정보를 담고 있다.
- 모눈종이의 사이즈
- 모눈종이 내의 스티커 모양
- 스티커의 크기 (모눈 종이 내 1의 개수)
따로 배열을 만들어 모든 정보들을 저장해도 되지만, 메모리 공간도 넉넉하니 구현하기 쉽도록 구조체를 이용하는 것이 가장 나을 것 같았다.
struct sticker{
pair<int,int> size;
int arr[15][15];
int stickerSize;
};
이렇게 만든 구조체들은 코드 내에서 배열로 관리하였다. 스티커는 들어오는 순서대로 부착 시도하기 때문이다.
struct sticker stickers[105];
2. 스티커 부착 가능 여부 확인
스티커가 부착 가능한지 확인하기 위해서는 다음과 같은 조건을 만족해야한다.
- 가능한 가장 위쪽에 붙여야 한다.
- 위쪽에 가능한 위치가 여러 개 있다면 가장 왼쪽의 위치를 선택한다.
이 때 주의해야 할 것은, 이 조건을 만족하기 위해 부착 가능 여부를 확인할 때 모눈 종이째로 확인해야 한다는 것이다.
배열의 위에서 부터 시작해 모눈 종이를 배치할 수 있는 곳에 모두 배치해보며 가능한 곳을 찾아야 한다. 부착 가능 여부는 조금 더 간단하게 하기 위해 그 기능을 따로 만들고, main 함수 내에서 반복문을 통해 모눈 종이를 배치한다.
부착 가능 여부 확인 함수는 스티커의 인덱스, 모눈 종이를 배치할 위치 정보를 받아 가능 여부를 확인한다.
스티커가 1인데 노트북도 1인 경우 (이미 부착되어 있는 경우)에는 바로 false를 반환하도록 한다.
만약 스티커가 정상적으로 부착될 수 있는 경우 노트북에 부착해주는 역할까지 맡아준다.
bool check(int n,int row, int col){
struct sticker tmp = stickers[n];
int lapCpy[45][45];
// check fittable
for(int i=0;i<tmp.size.first;i++){
for(int j=0;j<tmp.size.second;j++){
if(laptop[row + i][col + j] == 1 && tmp.arr[i][j] == 1) return false;
}
}
for(int i=0;i<tmp.size.first;i++){
for(int j=0;j<tmp.size.second;j++){
if(tmp.arr[i][j] == 1)laptop[row+i][col+j] = tmp.arr[i][j];
}
}
return true;
}
3. 스티커의 회전
문제의 핵심이다. 스티커는 모눈종이에 부착되어 있다. 모눈 종이는 행렬과 같다. 따라서 행렬을 회전 하는 방법을 알아야 한다.
우선 3*3 배열을 먼저 살펴보자.
1 2 3
4 5 6
7 8 9
----- 시계 방향 90도 회전
7 4 1
8 5 2
9 6 3
각 위치별로 이동한 좌표를 살펴보면 다음과 같다.
(0,0) → (0,2) (0,1) → (1,2) (0,2) → (2,2)
(1,0) → (0,1) (1,1) → (1,1) (1,2) → (2,1)
(2,0) → (0,0) (2,1) → (1,0) (2,2) → (2,0)
규칙을 살펴보면.. 일반적으로 2차원 배열을 순회할 수 있는 반복문을 기준으로 순서를 살펴보면 된다.
[i][j]로 표기하고 [0][0] → [0][1] → [0][2] → [1][0] → …의 순서로 살펴보자.
(0,0) → (0,2) (0,1) → (1,2) (0,2) → (2,2)
[i]는 1씩 증가하고 있다. (0,1,2) [j] 는 2로 고정되어 있다.
(1,0) → (0,1) (1,1) → (1,1) (1,2) → (2,1)
[i]는 증가하고 있다. (0,1,2) [j]는 1로 고정되어 있다.
(2,0) → (0,0) (2,1) → (1,0) (2,2) → (2,0)
[i] 는 증가하고 있다. [j] 는 0으로 고정되어 있다.
이 사이의 관계를 자세히 보면, i 는 모두 0,1,2,3으로 증가하고 있다.
반면, j 는 고정되어 있는데, 회전하기 전의 i 값이 j 값에 영향을 주는 것을 확인할 수 있다.
즉, 회전하기 전에 0 행이었던 것이 2열이 되었고, 1행이었던 것이 1열이 되었고, 2행이었던 것들이 0 행이 되었다. 이를 식으로 나타내면
//
for(int i=0;i<beforeRow;i++){
for(int j=0;j<beforeCol;j++){
after[j][beforeRow - i - 1] = before[i][j];
}
}
따라서 회전 함수는 다음과 같다.
void rotateSticker(int n){
struct sticker *tmp = &stickers[n];
int matrix[15][15];
for(int i=0;i<tmp->size.first;i++){
for(int j=0;j<tmp->size.second;j++){
matrix[i][j] = tmp->arr[i][j];
}
}
for(int i=0;i<tmp->size.first;i++){
for(int j=0;j<tmp->size.second;j++){
tmp->arr[j][tmp->size.first - i - 1] = matrix[i][j];
}
}
int ch;
ch = tmp->size.first;
tmp->size.first = tmp->size.second;
tmp->size.second = ch;
}
주목해야 할 것은 돌리고 난 뒤 N * M 은 M * N 으로 바뀌었음으로 구조체 내의 변수를 바꿔줘야 한다.
int ch;
ch = tmp->size.first;
tmp->size.first = tmp->size.second;
tmp->size.second = ch;
전체 코드는 다음과 같다.
#include <iostream>
using namespace std;
int N, M, K;
struct sticker{
pair<int,int> size;
int arr[15][15];
int stickerSize;
};
struct sticker stickers[105];
int laptop[45][45];
bool check(int n,int row, int col){
struct sticker tmp = stickers[n];
int lapCpy[45][45];
// check fittable
for(int i=0;i<tmp.size.first;i++){
for(int j=0;j<tmp.size.second;j++){
if(laptop[row + i][col + j] == 1 && tmp.arr[i][j] == 1) return false;
}
}
for(int i=0;i<tmp.size.first;i++){
for(int j=0;j<tmp.size.second;j++){
if(tmp.arr[i][j] == 1)laptop[row+i][col+j] = tmp.arr[i][j];
}
}
return true;
}
void rotateSticker(int n){
struct sticker *tmp = &stickers[n];
int matrix[15][15];
for(int i=0;i<tmp->size.first;i++){
for(int j=0;j<tmp->size.second;j++){
matrix[i][j] = tmp->arr[i][j];
}
}
for(int i=0;i<tmp->size.first;i++){
for(int j=0;j<tmp->size.second;j++){
tmp->arr[j][tmp->size.first - i - 1] = matrix[i][j];
}
}
int ch;
ch = tmp->size.first;
tmp->size.first = tmp->size.second;
tmp->size.second = ch;
}
int main(){
cin >> N >> M >> K;
int answer = 0;
//input
for(int i=0;i<K;i++){
struct sticker tmp;
tmp.stickerSize = 0;
cin >> tmp.size.first >> tmp.size.second;
for(int i=0;i<tmp.size.first;i++){
for(int j=0;j<tmp.size.second;j++){
cin >> tmp.arr[i][j];
if(tmp.arr[i][j] == 1){
tmp.stickerSize++;
}
}
}
stickers[i] = tmp;
}
for(int x=0;x<K;x++){
int rotate = 4;
//struct sticker cur = stickers[x];
bool flag = false;
while(rotate--){
struct sticker cur = stickers[x];
int rowT, colT;
rowT = N - (cur.size.first-1);
colT = M - (cur.size.second-1);
for(int i = 0 ; i < rowT; i++){
for(int j=0 ; j < colT;j++){
if(check(x,i,j)){
flag = true;
answer += cur.stickerSize;
break;
}
}
if(flag) break;
}
if(flag) break;
else rotateSticker(x);
}
}
cout << answer << "\n";
return 0;
}
댓글남기기