[백준 18808] 스티커 붙이기

https://www.acmicpc.net/problem/18808

18808번: 스티커 붙이기

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, K;
int sticker[10 + 2][10 + 2];
int laptop[40 + 2][40 + 2];
int r_tmp[10 + 2][10 + 2];	// 회전 결과 저장용 배열 
int r, c;	// 스왑때문에 전역으로 선언	// 이거 인자로 받아서 진행하면 안바뀜 ;


int cnt_area()
{
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			//printf("%d ", laptop[i][j]);
			if (laptop[i][j] == 1) cnt++;
		}
		//printf("\n");
	}
	return cnt;
}



void rotate_it()
{
	std::fill(&r_tmp[0][0], &r_tmp[0][0] + sizeof(r_tmp) / sizeof(int), 0);		//회전용 임시 배열 초기화 

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			r_tmp[j][r - i - 1] = sticker[i][j];
		}
	}
	int tmp = r;
	r = c;
	c = tmp;

	std::fill(&sticker[0][0], &sticker[0][0] + sizeof(sticker) / sizeof(int), 0);		// 스티커배열 초기화 
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			sticker[i][j] = r_tmp[i][j];
		}
	}
}



bool chk_n_fill(int x, int y)
{
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			// 노트북에 자리 없으면 리턴 false
			if (laptop[i + x][j + y] == 1 && sticker[i][j] == 1) return false;
		}
	} 

	// 루프 다 돌았는데 리턴 안됐으면 스티커 붙일 수 있는 것임 
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (sticker[i][j]) laptop[i + x][j + y] = sticker[i][j];
		}
	}
	return true;
}



void attach_it()
{
	int dir = 0;
	while (dir < 4) {
		if (dir != 0) rotate_it();
		for (int i = 0; i <= N - r; i++) {
			for (int j = 0; j <= M - c; j++) {
				if (chk_n_fill(i, j)) return;
			}
		}
		dir++;
	}
}


void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < K; i++) {	// K개의 스티커 붙인다
		r = 0; c = 0;
		scanf("%d %d", &r, &c);
		std::fill(&sticker[0][0], &sticker[0][0] + sizeof(sticker) / sizeof(int), 0);
		for (int j = 0; j < r; j++) {
			for (int k = 0; k < c; k++) {
				scanf("%d", &sticker[j][k]);
			}
		}
		attach_it();
	}
}


int main()
{
	input();
	int ans = cnt_area();
	printf("%d", ans);
	return 0;
}

드디어 붙였다 스티커...ㅂㄷㅂㄷ 

나의 머가리로는 스티커 붙이는 것도 어렵다고요... 

 

// input( ) 함수

원래는 3차원 배열에 받아서 하다가 헷갈려서 관뒀다. 다음에 복습할 때는 3차원 배열에 받아서 다시 짜봐야지.. 

아무튼 스티커 배열을 입력받으면서 이것을 붙일 수 있는지 없는지 확인해주었기 때문에, 입력받기 전 마다 sticker 배열을 초기화 해줬다. 

 

 

// attach_it( ) 함수

회전을 4번(0, 90, 180, 270) 하면서 해당 스티커를 붙일 수 있는지 없는지 판단해야 하기 때문에 dir을 0~3까지만 돌려주었다. while루프를 빠져나오면 해당 스티커는 회전하여도 붙일 수 없는 것이기 때문에 버려야 한다. 

 

여기서 중요한 점은 (노트북의 가로길이 - 스티커 가로길이) , (노트북 세로길이 - 스티커 세로길이) 만큼만 루프를 돌려주었다는 것이다. 스티커를 붙일 수 있는 공간(다시말해 스티커의 시작좌표)을 이렇게 한정해 두면 따로 영역체크를 하지 않아도 된다. 그리고 회전하여도 그때마다 r,c 값이 바뀌기 때문에 혼동되지 않는다. 

 

 

// chk_n_fill( ) 함수

attach_it 함수 내의 루프를 돌면서 해당 위치에 스티커를 붙일 수 있는지 없는지 확인하고, 있다면 스티커를 붙이는 함수이다. 

스티커를 붙일 수 있는지 없는지 여부는 파악하기 쉽다. 노트북의 해당 영역에 이미 스티커가 붙여져 있는데(laptop[i + x][j + y] == 1), 스티커를 붙이려고 하면(sticker[i][j] == 1) 안된다. 이때는 더이상 탐색하지 않아도 되기 때문에 바로 false를 리턴하면서 함수를 빠져나온다. 

 

반면 루프를 다 돌았는데도 함수를 빠져나가지 않았다면, 노트북의 해당 위치에 스티커를 붙일 수 있는 것이다. 이때 또 주의해야 할 점은, 스티커를 입력 받을 때 진짜 스티커가 있는 부분(1) 과 모눈종이(0)를 같이 입력받기 때문에, 노트북에 붙일 때는 스티커 + 모눈 종이 영역을 그냥 가져다 붙이는 것이 아니라 스티커 부분만 붙여야 한다. 따라서 " if(sticker[i][j]) " 이 조건이 추가되어야 한다. (경험을 통한 .. ^^.. 코멘트 .. ^^..)

 

 

// rotate( ) 함수

90도 씩 돌리는 함수이다. 돌리는건 쉬웠는데 r, c(스티커의 가로 세로 길이) 스왑하는 것 때문에 애좀먹었다(이렇게 스왑한 변수를 다른 함수에도 적용해야 되기 때문....). 생각하기 어려워요.. 이 rotate 함수 때문에 r과 c를 전역으로 선언하였다. 파라미터로 받아서 스왑하면 안바뀐다. 주소값 쓰면 될텐데 내 머가리로는 거기까지는 정말 한계치 이상이므로 그냥 전역변수로 선언하고, 데이터 입력 받을 때 마다 초기화 해줬다. ㅋㅋㅋㅋ

이때, 스티커가 여러개 들어오므로 회전용 임시배열 r_tmp와 스티커배열 sticker를 초기화해주는 것을 잊지말자 !