[Algorithm] BOJ 18808 스티커 붙이기

tree9295·2020년 3월 25일

18808 algorithm boj 스티커 붙이기 알고리즘

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

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;
}

느낀점

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