Syureu

찍먹을 좋아하는 사람.

BOJ 18808 스티커 붙이기

5 분 소요

1 - 스티커 붙이기 (https://www.acmicpc.net/problem/18808)

문제를 후기 포스팅 작성 시점 기준으로 확인 할 수 없는데(대회 마감의 사유로), 잠결에 읽으면서 들었던 생각

  • A형에는 두 문제가 나오는데 보통 상대적으로 쉬운 하나, 그리고 상대적으로 어려운 하나
  • 이 문제는 쉬운 하나에 속하며 최근 경향으로는 시뮬레이션인 문제가 주로 나옴
  • 그런 트렌드에 잘 맞아 떨어지는 시뮬레이션 문제로 판단

용어 정리

맵 : n * m의 스티커를 붙이는 판떼기 (int v[40][40])

분석과 접근

문제를 읽어보면 다음과 같다.

  1. k개의 스티커를 주어지는 순서대로 붙여보기를 시도한다
  2. 최대한 위쪽, 왼쪽편으로 붙이기를 시도하며 빈공간이 있다면 붙인다
  3. 만약 해당 모양으로 붙일 수 없다면 90도 시계방향을 돌려 2를 시도
  4. 360도 회전 다 할 때 까지 못 붙인다면 스티커는 버린다(예?)
  5. 그렇게 주어진 k개의 스티커 중 붙일 수 있는걸 조건대로 다 붙인다면 최종적으로 맵에 몇개의 칸에 스티커가 붙었는가?

시뮬레이션 문제라고 판단한 만큼 분석한 그대로 접근하여 따라해보기를 시도

1. main

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	while (k--) {
		cin >> r >> c;
		vector<vector<int>>stk(r);
		for (int i = 0; i < r; ++i) {
			stk[i].resize(c);
			for (int j = 0; j < c; ++j) cin >> stk[i][j];
		}
		for (int i = 0; i < 4; ++i) {
			if (is_can(stk)) {
				do_stk(stk);
				break;
			}
			if (i != 3) stk = turn_stk(stk);
		}
	}
	cout << ans;
}

입력 받고 스티커 들어오는대로 is_can() 함수를 통해 붙일 수 있는지를 판단하고

  • 붙일 수 있다면 do_stk()를 통해 붙이고 넘기기
  • 붙일 수 없다면 turn_stk()를 통해 90도 회전을 시도. 다만 0도, 90도, 180도, 270도 회전하고도 안된다면 그 스티커는 아예 안되니까 넘기기

2. is_can()

bool is_can(vector<vector<int>>& stk) {
	bool flag1 = 0;
	int stkxsize = stk.size();
	for (int i = 0; (i <= n - stkxsize) && !flag1; ++i) {
		int stkysize = stk[0].size();
		for (int j = 0; (j <= m - stkysize) && !flag1; ++j) {
			bool flag2 = 0;
			for (int k = 0; k < stkxsize && !flag2; ++k) {
				for (int l = 0; l < stkysize && !flag2; ++l) {
					if (!stk[k][l])continue;
					if (v[i + k][j + l]) {
						flag2 = 1;
						break;
					}
				}
			}
			if (!flag2) {
				flag1 = 1;
				canx = i;
				cany = j;
				break;
			}
		}
	}
	if (flag1) return true;
	return false;
}

flag1은 스티커를 붙일 수 있나 없나 체크하는 변수
flag2는 i, j 일때 스티커를 붙일 수 있는가 없는가를 나타내는 변수

  1. 스티커를 붙일 수 있는가 없는가 확인을 위해 우선 i, j 인덱스를 통해 스티커의 왼쪽 위 지점의 위치를 결정
  2. 스티커를 붙이게 되는 우선순위가 위쪽, 왼쪽 순이기 때문에 흔히 2차원 배열을 순회하는 방법 그대로 찾아보다가 나오는 첫번째 가능한 위치가 있다면 거기 붙여주면 된다
  3. i, j 마다, 스티커 사이즈만큼 k, l을 통해 스티커를 순회하고
  4. 스티커가 없는 자리는(stk[k][l]==0이라면) 확인 할 필요가 없고
  5. 스티커가 있는 자리는(stk[k][l]==1) 스티커 붙이는 판떼기의 그자리가 비어있다면 상관이 없다 (flag2==false 유지)
  6. 다만 그 자리에 다른 스티커를 이미 붙여놨다면(v[i+k][j+l]==1) 지금의 i, j에서는 스티커를 붙이지 못한다는 것이니 다음 인덱스로 넘어가도록 한다. 이때 flag2=true로해서, 현 위치에 붙이지 못하는 것을 뒤에서 알려주자

결과적으로 is_can() 안에서 i, j 일때 flag2 = false로 유지 되었다면, 이는 스티커를 붙일 자리에 스티커가 없다는 의미로 붙일 수 있다는 의미이다. 붙일 수 있다면 해당 자리에 스티커 붙이기 위해 전역변수 canx, cany로 i, j를 넘겨주고 이 함수가 true를 반환 할 수 있도록 하자.
만약 i, j를 다 돌았는데도 flag1 = false라면 어떤 i, j에서도 스티커를 붙일 수 없다는 의미이고, false를 통해 붙일 수 없음을 리턴하자.

i, j, k, l 의 인덱스를 조정하는게 힘들다면 인덱스를 쪼물딱 대는 연습을 많이 해보자. 물론 이 문제에서 가장 어려운 부분은 여기가 아니지만.. 여기도 힘들다면 이차원 배열과 구현, 시뮬레이션 계열 문제를 많이 접해 인덱스를 원하는대로 굴리는 것에 익숙해지는게 좋다.

3.do_stk()

void do_stk(vector<vector<int>>& stk) {
	for (int i = 0; i < stk.size(); ++i) {
		for (int j = 0; j < stk[0].size(); ++j) {
			if (stk[i][j]) {
				v[canx + i][cany + j] = 1;
				ans++;
			}
		}
	}
}

메인에서 is_can()을 통해 붙일 수 있다면 do_stk()를 호출해 실제로 붙여주는 작업을 하자. 말그대로 스티커 범위를 돌면서 스티커가 있는 자리면 실제 맵에 붙이는 처리를 해준다.

붙이는 처리를 다 한다음 전체 맵에서 몇개 붙었나 세도 아무 상관이 없지만, 이 문제는 붙이기만 하면 끝까지 해당 스티커 갯수에는 변동이 없어서 붙일 때마다 한장씩 카운팅 해줬다. (사실 끝나고 2차원 배열 순회하기가 귀찮았다는게 학계의 정설이다)

4. turn_stk()

vector<vector<int>> turn_stk(vector<vector<int>>& stk) {
	vector<vector<int>>turned(stk[0].size());
	for (int i = 0; i < turned.size(); ++i) turned[i].resize(stk.size());
	for (int i = 0; i < turned.size(); ++i) {
		for (int j = 0; j < turned[0].size(); ++j) {
			turned[i][j] = stk[stk.size() - 1 - j][i];
		}
	}
	return turned;
}

스티커를 붙일 수가 없어서 90도를 회전할 경우 turn_stk()를 호출한다. 돌리기가 실제로는 자주 할 일이 없는데 A형에서는 기출도 있고 어느정도 그냥 해야하는 테크닉으로 보인다.(자매품 배열회오리도 있다)
정처기 등에서 알고리즘 파트를 공부하면 2차원 배열 5*5를 시계방향으로 돌려라 같은 문제가 있는데 이러한 문제는 보통 N * N 이라 인덱스 조절이 어렵지 않은데 위 문제, 그리고 삼성 기출등은 N * M의 배열을 돌리는 경우가 있다.
N * M을 90도로 돌리면 M * N가 된다. 주의하자. 대부분 r, c로 스티커의 크기를 받았을 텐데 그렇다면 c, r로 동작하도록 바꿔줘야 된다. 이 부분에서 실수해서 틀린사람이 꽤 있다고 바킹독님 해설 강의때 봤다.

나는 회전한 stk를 새로 만들어서 stk에 덮었기 때문에 아래의 코드들에서도 r, c가 아닌 stk.size(), stk[0].size()를 인덱스 범위 잡는데 기준으로 사용했다.

그리고 실제로 돌리는 파트

turned[i][j] = stk[stk.size() - 1 - j][i];

일단 이문제 풀때는 종이에 인덱스 적어가면서 규칙을 찾았다.
나도 이런걸 다 외우면서 하지는 않는데 막상 필요할 때 할려고 하면 잘 안나온다. 더군다나 N * N 같은 깔끔한 배열도 아니고 N * M 등이면 인덱스가 굉장히 커찮다. 90도 시계 반시계등은 레퍼런스를 준비하는것도 A형 대비로 좋은게 아닐까 싶다.

소스

#include<iostream>
#include<vector>
using namespace std;
int n, m, k, r, c, v[40][40], canx, cany, ans;
vector<vector<int>> turn_stk(vector<vector<int>>& stk) {
	vector<vector<int>>turned(stk[0].size());
	for (int i = 0; i < turned.size(); ++i) turned[i].resize(stk.size());
	for (int i = 0; i < turned.size(); ++i) {
		for (int j = 0; j < turned[0].size(); ++j) {
			turned[i][j] = stk[stk.size() - 1 - j][i];
		}
	}
	return turned;
}
void do_stk(vector<vector<int>>& stk) {
	for (int i = 0; i < stk.size(); ++i) {
		for (int j = 0; j < stk[0].size(); ++j) {
			if (stk[i][j]) {
				v[canx + i][cany + j] = 1;
				ans++;
			}
		}
	}
}
bool is_can(vector<vector<int>>& stk) {
	bool flag1 = 0;
	int stkxsize = stk.size();
	for (int i = 0; (i <= n - stkxsize) && !flag1; ++i) {
		int stkysize = stk[0].size();
		for (int j = 0; (j <= m - stkysize) && !flag1; ++j) {
			bool flag2 = 0;
			for (int k = 0; k < stkxsize && !flag2; ++k) {
				for (int l = 0; l < stkysize && !flag2; ++l) {
					if (!stk[k][l])continue;
					if (v[i + k][j + l]) {
						flag2 = 1;
						break;
					}
				}
			}
			if (!flag2) {
				flag1 = 1;
				canx = i;
				cany = j;
				break;
			}
		}
	}
	if (flag1) return true;
	return false;
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	while (k--) {
		cin >> r >> c;
		vector<vector<int>>stk(r);
		for (int i = 0; i < r; ++i) {
			stk[i].resize(c);
			for (int j = 0; j < c; ++j) cin >> stk[i][j];
		}
		for (int i = 0; i < 4; ++i) {
			if (is_can(stk)) {
				do_stk(stk);
				break;
			}
			if (i != 3) stk = turn_stk(stk);
		}
	}
	cout << ans;
}

참고