[C++] 백준 14500번: 테트로미노

이 문제를 풀기위해 기하학적 상상력을 채워줄 블럭을 직접 만들었다.

문제 바로가기

 

⛳문제에서 요구하는 것⛳

1. 크기가 N×M인 종이 위에 테트로미노 하나를 놓는다.

2. 테트로미노가 놓인 칸에 쓰여있는 수들의 합의 최대값을 알아보자.

3. 테트로미노를 회전, 대칭을 시켜도 된다.

 

🧨주어진 조건🧨

1. 4 ≤ N, M ≤ 500

2. 각 칸의 입력은 1000 미만의 자연수다.

 

 

✨처음 생각한 풀이✨

1. 각 점을 방문한다.

2. 다섯가지의 테트로미노에 대해, 

  3. 기준 위치를 방문한 점에 놓고

  4. 90도씩 회전시키며 테트로미노가 놓인 칸에 쓰여있는 수의 합을 구한다.

  5. 이번엔 좌우, 상하 대칭을 시켜서 확인한다.

    - 그런데, 테트로미노가 놓인 칸을 어떻게 알아내냐가 관건이다.

    - 나는 각 테트로미노의 기준 위치를 (0, 0)으로 두고, 그 테트로미노를 구성하는 다른 위치를 상대적인 좌표로 나타냈다.

    - 그 후, 방문한 점(r, c)에 각 위치를 더한 (r + dr[0], c + dc[0])과 같은 식으로 위치를 구했다.

    - 회전, 대칭은 아래 내용을 참고했다.

👁‍🗨 점의 회전과 대칭에 대하여
    * 아래는 r, c축이 각각 아래, 우측 방향으로 증가하는 좌표계 기준이다.
  점 (r, c)를 \(\theta\)만큼 회전했을 때 변화한 좌표는 \((c\sin\theta+r\cos\theta,c\cos\theta-r\sin\theta)\)이다.
  점 (r, c)를 r축으로 대칭하면 (r, -c), c축으로 대칭하면 (-r, c)이며 r = c 직선을 기준으로 대칭하면 (c, r)이다.

 

#include <iostream>
#include <utility>

using namespace std;

#define EL "\n"
#define FOR(i, j) for(int i = 0; i < j; i++)

int N, M;
int maxSum = 0;
int table[500][500];

const int types[5][4][2] = { { {0,0}, {0,1}, {0,2}, {0,3} },		// I
				   { {0,0}, {0,1}, {1,0}, {1,1} },		// O
				   { {0,0}, {1,0}, {2,0}, {2,1} },		// L
				   { {0,0}, {1,0}, {1,1}, {2,1} },		// S
				   { {0,0}, {0,1}, {0,2}, {1,1} } };		// T

bool isInTable(pair<int, int> pos) {
	return pos.first < N&& pos.first >= 0 && pos.second < M&& pos.second >= 0;
}

pair<int, int> rotate(int r, int c, int angle) {
	pair<int, int> newPos;
	switch (angle) {
	case 0:
		newPos = make_pair(r, c);
		break;
	case 90:
		newPos = make_pair(c, -r);
		break;
	case 180:
		newPos = make_pair(-r, -c);
		break;
	case 270:
		newPos = make_pair(-c, r);
		break;
	}
	return newPos;
}

pair<int, int> symmetricize(int r, int c, char axis) {
	pair<int, int> newPos;
	switch (axis) {
	case 0:
		newPos = make_pair(r, c);
		break;
	case 'c':
		newPos = make_pair(-r, c);
		break;
	case 'r':
		newPos = make_pair(r, -c);
		break;
	}
	return newPos;
}

void putOn(const int type[4][2], int r, int c) {
	int angles[4] = { 0, 90, 180, 270 };
	for (int& angle : angles) {
		int sum = 0;
		FOR(i, 4) {
			pair<int, int> delta = rotate(type[i][0], type[i][1], angle);
			pair<int, int> pos = make_pair(r + delta.first, c + delta.second);
			if (isInTable(pos)) {
				sum += table[pos.first][pos.second];
			}
			else goto NEXT1;
		}
		maxSum = sum > maxSum ? sum : maxSum;
	NEXT1:;
	}

	char axises[2] = { 'c', 'r' };
	for (char& axis : axises) {
		int sum = 0;
		FOR(i, 4) {
			pair<int, int> delta = symmetricize(type[i][0], type[i][1], axis);
			pair<int, int> pos = make_pair(r + delta.first, c + delta.second);
			if (isInTable(pos)) {
				sum += table[pos.first][pos.second];
			}
			else goto NEXT2;
		}
		maxSum = sum > maxSum ? sum : maxSum;
	NEXT2:;
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	FOR(r, N)
		FOR(c, M)
		cin >> table[r][c];

	FOR(r, N)
		FOR(c, M)
		for (auto& type : types)
			putOn(type, r, c);

	cout << maxSum << EL;

	return 0;
}

 

👓결과와 문제점 분석👓

결과: 틀렸습니다.

1. 반례가 있다.

4 4
0 0 0 0
0 0 0 0
0 1 0 0
0 2 3 4
정답: 10
오답: 9

  - L자 모양을 대칭시킨 뒤, 회전을 시켜야 해당 모양이 나온다.

2. 나는 대칭을 시킨 테트로미노를 회전을 시키지 않았다.

3. 또한 불필요한 반복이 여럿 있었다.

  - O, I 모양에서는 대칭을 시키는 것이 의미가 없다.

  - r축 대칭과 c축 대칭을 서로 회전하면 일치한다.

  - r = c 직선을 기준으로 대칭을 한 번만 수행하면 된다.

 

이를 반영하여 수정한 디버그 코드는 아래와 같다.

#include <iostream>
#include <utility>

using namespace std;

#define EL "\n"
#define FOR(i, j) for(int i = 0; i < j; i++)

int N, M;
int maxSum = 0;
int table[500][500];

const int types[5][4][2] = { { {0,0}, {0,1}, {0,2}, {0,3} },		// I
				   { {0,0}, {0,1}, {1,0}, {1,1} },		// O
				   { {0,0}, {1,0}, {2,0}, {2,1} },		// L
				   { {0,0}, {1,0}, {1,1}, {2,1} },		// S
				   { {0,0}, {0,1}, {0,2}, {1,1} } };		// T

bool isInTable(pair<int, int> pos) {
	return pos.first < N&& pos.first >= 0 && pos.second < M&& pos.second >= 0;
}

pair<int, int> rotate(int r, int c, int angle) {
	pair<int, int> newPos;
	switch (angle) {
	case 0:
		newPos = make_pair(r, c);
		break;
	case 90:
		newPos = make_pair(c, -r);
		break;
	case 180:
		newPos = make_pair(-r, -c);
		break;
	case 270:
		newPos = make_pair(-c, r);
		break;
	}
	return newPos;
}

pair<int, int> symmetricize(int r, int c, int axis) {
	pair<int, int> newPos;
	switch (axis) {
	case 0:
		newPos = make_pair(r, c);
		break;
	case 1:
		newPos = make_pair(c, r);
		break;
	}
	return newPos;
}

int _table[500][500];

void _init() {
	FOR(r, 500)
		FOR(c, 500)
		_table[r][c] = -1;
}

void putOn(const int type[4][2], int r, int c) {

	cout << "At (" << r << "," << c << ") ";
	char _types[5] = { 'I', 'O', 'L', 'S', 'T' };
	char _type;
	FOR(_i, 5)
		if (type == types[_i])
			_type = _types[_i];
	cout << _type << EL;

	int axises[2] = { 0, 1 };
	for (int& axis : axises) {


		if (axis == 0)
			cout << "  Not Symmetry..." << EL;
		else
			cout << "  Symmetry relative to rc-axis..." << EL;


		int angles[4] = { 0, 90, 180, 270 };
		for (int& angle : angles) {


			_init();
			cout << "    Rotation " << angle << " degrees..." << EL;


			int sum = 0;
			FOR(i, 4) {
				pair<int, int> symmetricized = symmetricize(type[i][0], type[i][1], axis);
				pair<int, int> delta = rotate(symmetricized.first, symmetricized.second, angle);
				pair<int, int> pos = make_pair(r + delta.first, c + delta.second);
				if (isInTable(pos)) {
					sum += table[pos.first][pos.second];
					_table[pos.first][pos.second] = table[pos.first][pos.second];
				}
				else goto NEXT;
			}
			maxSum = sum > maxSum ? sum : maxSum;


			FOR(_r, N) {
				cout << "      ";
				FOR(_c, M) {
					if (_table[_r][_c] == -1)
						cout << ".";
					else
						cout << _table[_r][_c];
				}
				cout << EL;
			}
			cout << "      sum: " << sum << EL;


		NEXT:;
		}

		if (_type == 'O' || _type == 'I')
			break;
	}
	cout << EL;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	FOR(r, N)
		FOR(c, M)
		cin >> table[r][c];

	FOR(r, N)
		FOR(c, M)
		for (auto& type : types)
			putOn(type, r, c);

	cout << maxSum << EL;

	return 0;
}

 

🎈정답 코드🎈

#include <iostream>
#include <utility>

using namespace std;

#define EL "\n"
#define FOR(i, j) for(int i = 0; i < j; i++)

int N, M;
int maxSum = 0;
int table[500][500];

const int types[5][4][2] = { { {0,0}, {0,1}, {0,2}, {0,3} },		// I
				   { {0,0}, {0,1}, {1,0}, {1,1} },		// O
				   { {0,0}, {1,0}, {2,0}, {2,1} },		// L
				   { {0,0}, {1,0}, {1,1}, {2,1} },		// S
				   { {0,0}, {0,1}, {0,2}, {1,1} } };		// T

bool isInTable(pair<int, int> pos) {
	return pos.first < N&& pos.first >= 0 && pos.second < M&& pos.second >= 0;
}

pair<int, int> rotate(int r, int c, int angle) {
	pair<int, int> newPos;
	switch (angle) {
	case 0:
		newPos = make_pair(r, c);
		break;
	case 90:
		newPos = make_pair(c, -r);
		break;
	case 180:
		newPos = make_pair(-r, -c);
		break;
	case 270:
		newPos = make_pair(-c, r);
		break;
	}
	return newPos;
}

pair<int, int> symmetricize(int r, int c, int axis) {
	pair<int, int> newPos;
	switch (axis) {
	case 0:
		newPos = make_pair(r, c);
		break;
	case 1:
		newPos = make_pair(c, r);
		break;
	}
	return newPos;
}

void putOn(const int type[4][2], int r, int c) {
	char _types[5] = { 'I', 'O', 'L', 'S', 'T' };
	char _type;
	FOR(_i, 5)
		if (type == types[_i])
			_type = _types[_i];

	int axises[2] = { 0, 1 };
	for (int& axis : axises) {
		int angles[4] = { 0, 90, 180, 270 };
		for (int& angle : angles) {
			int sum = 0;
			FOR(i, 4) {
				pair<int, int> symmetricized = symmetricize(type[i][0], type[i][1], axis);
				pair<int, int> delta = rotate(symmetricized.first, symmetricized.second, angle);
				pair<int, int> pos = make_pair(r + delta.first, c + delta.second);
				if (isInTable(pos)) {
					sum += table[pos.first][pos.second];
				}
				else goto NEXT;
			}
			maxSum = sum > maxSum ? sum : maxSum;
		NEXT:;
		}

		if (_type == 'O' || _type == 'I')
			break;
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> M;

	FOR(r, N)
		FOR(c, M)
		cin >> table[r][c];

	FOR(r, N)
		FOR(c, M)
		for (auto& type : types)
			putOn(type, r, c);

	cout << maxSum << EL;

	return 0;
}