[C++] BOJ(백준) 4920 테트리스 게임

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

4920번: 테트리스 게임

 

구현 문제다.

 

설명

이런 테트리스 문제는 전에도 접한 경험이 있다.

이전에는 모든 모양에 대해 각각 반복문을 돌리는 방법으로 해결했다.

그러나 그건 코드적으로는 효율적이어도 너무 단순 노동이라는 생각이 들어 효율적으로 해결하고 싶었다.

 

여러 방법을 떠올려 보면서 남자친구에게서 좋은 방법을 얻었다.

BFS에서 사용하던 툴을 이용하는 것이다. 배열의 칸에 대한 정보를 dr, dc 배열에 저장한다.

그리고 테트리스 블록 각각을 돌리는 것이 아닌 배열 자체를 회전 시키는 것이다.

 

정말 좋은 방법이라고 생각해 구현을 시도하려 했는데 5중 반복문이 필요한 걸 깨달았다.

작은 수가 돌아가기에 시간적 문제는 없다고 생각했지만 개선 방법을 찾고 싶었다.

또, 모든 블록이 4가지 방향에서 다른 모양을 가지는 것이 아니기 때문에 20개의 모양을 고려하면 중복되는 부분이 생긴다.

 

블록의 회전을 고려하면 총 13가지의 경우가 생긴다.

이 13가지의 경우를 위의 BFS 방법처럼 dr, dc 배열에 2차원으로 저장했다.

그리고 이 13가지 경우에 대해 완전 탐색을 진행했다.

 

완전 탐색의 경우에서도 두 가지 의견이 존재했다.

BFS처럼 큐를 이용하고, 오른쪽, 아래로 탐색을 진행한다. 이 때, 범위를 벗어나는 경우 큐에 집어넣지 않는다.

이걸 활용해 이중 반복문으로 범위를 벗어나는 순간 break를 걸었다.

 

---

 

최종코드

#include <iostream>
using namespace std;

int arr[100][100];

int dr[13][4] = {
	{0, 0, 0, 0},
	{0, 0, 1, 1},
	{0, 0, 0, 1},
	{0, 0, 0, 1},
	{0, 0, 1, 1},
	{0, 1, 2, 3},
	{0, 1, 1, 2},
	{0, 1, 2, 2},
	{0, 1, 1, 1},
	{0, 0, 1, 2},
	{0, 1, 1, 2},
	{0, 1, 1, 1},
	{0, 1, 1, 2}
};

int dc[13][4] = {
	{0, 1, 2, 3},
	{0, 1, 1, 2},
	{0, 1, 2, 2},
	{0, 1, 2, 1},
	{0, 1, 0, 1},
	{0, 0, 0, 0},
	{1, 1, 0, 0},
	{1, 1, 1, 0},
	{0, 0, 1, 2},
	{0, 1, 0, 0},
	{1, 0, 1, 1},
	{1, 0, 1, 2},
	{0, 0, 1, 0}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int cnt = 1;
	while (1) {
		int n;	cin >> n;
		if (n == 0) break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) cin >> arr[i][j];

		int res = -10000000;

		for (int k = 0; k < 13; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					bool flag = false;
					int tmp = 0;
					for (int w = 0; w < 4; w++) {
						int r = i + dr[k][w];
						int c = j + dc[k][w];

						if (r < 0 || r >= n || c < 0 || c >= n) {
							flag = true;
							break;
						}

						tmp += arr[r][c];
					}
					if (flag) break;
					res = max(res, tmp);
				}
			}
		}
		cout << cnt << ". " << res << "\n";
		cnt++;
	}
}

 

---

 

회고

사실 이 문제를 풀기 전에 방법을 생각해보고, 구글링으로 코드도 찾아봤다.

대부분의 코드가 13가지 경우의 수에 대해 각각의 반복문을 돌린 코드였다.

내가 푼 방법이 효율적이고 가독성이 있다고 확신할 순 없지만 획기적이라곤 생각한다.