[BOJ] 18808 - 스티커 붙이기

[백준] 18808 - 스티커 붙이기

풀이 시간 : 61분정도.
N과 M의 크기가 작고 스티커를 확인하는 순서가 정해져 있기 때문에 시간복잡도가 넉넉하다. 즉 그냥 완전탐색으로 풀면 된다.
구현하다가 헷갈리는 일이 없도록 스티커를 붙일 수 있는지 확인하는 함수와 스티커를 붙이는 함수를 따로 빼서 정의했다.
자꾸 i와 j를 헷갈린다던지 R과 C를 바꿔 쓴다던지 하는 오타 때문에 약간 헤맸다.
시간복잡도를 생각하지 않아도 되고 구현 난이도도 높지 않아 행복하게 풀었던 문제다. 그러나…

소스코드

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

int n, m, k, notebook[45][45];
vector<vector<int>> sticker;

bool is_in_range(int x, int y) {
	return x >= 0 && x < n&& y >= 0 && y < m;
}

bool is_attachable(int x, int y, int mode) {
	bool rtn = true;
	int R = sticker.size() - 1, C = sticker[0].size() - 1;
	for (int i = 0; i <= R; i++) {
		for (int j = 0; j <= C; j++) {
			if (sticker[i][j] == 0) continue;
			int r = mode == 0 ? x + i : mode == 1 ? x + j :
				mode == 2 ? x + R - i : x + C - j;
			int c = mode == 0 ? y + j : mode == 1 ? y + R - i :
				mode == 2 ? y + C - j : y + i;
			if (!is_in_range(r, c) || notebook[r][c]) {
				rtn = false;
				break;
			}
		}
	}
	return rtn;
}

int attach(int x, int y, int mode) {
	int rtn = 0;
	int R = sticker.size() - 1, C = sticker[0].size() - 1;
	for (int i = 0; i <= R; i++) {
		for (int j = 0; j <= C; j++) {
			if (sticker[i][j] == 0) continue;
			int r = mode == 0 ? x + i : mode == 1 ? x + j :
				mode == 2 ? x + R - i : x + C - j;
			int c = mode == 0 ? y + j : mode == 1 ? y + R - i :
				mode == 2 ? y + C - j : y + i;
			notebook[r][c] = 1;
			rtn++;
		}
	}
	return rtn;
}

int go() {
	int cnt = 0;
	for (int mode = 0; mode < 4; mode++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (is_attachable(i, j, mode)) {
					cnt += attach(i, j, mode);
					return cnt;
				}
			}
		}
	}
	return cnt;
}

int main(void) {
	int ans = 0;
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < k; i++) {
		vector<vector<int>>().swap(sticker);
		int r, c;
		scanf("%d %d", &r, &c);
		// 스티커를 입력받는다.
		sticker.resize(r);
		for (int j = 0; j < r; j++) {
			int buf;
			for (int k = 0; k < c; k++) {
				scanf("%d", &buf);
				sticker[j].push_back(buf);
			}
		}
		ans += go();
	}
	printf("%d", ans);
	return 0;
}