[BOJ][삼성기출] 14500. 테르로미노

문제

테르노미노

문제 접근

5개의 모형에 대해 회전하는 모든 경우의 수를 배열에 저장하여 시뮬레이션 돌렸다.
사실 풀면서도 이건 아닌 거 같다는 생각이 들었지만,, 별다른 방법이 생각나지 않았고 문제를 풀긴 했다.

관건1. DFS로 접근하기

위 그림처럼 ㅜ 모양을 제외한 나머지 블럭은 depth가 3인 DFS로 풀면 쉽게 풀 수 있는 거였다!
DFS의 인자로 x좌표, y좌표, count, sum 을 주면 될 것 같다.

ㅜ의 경우 내가 푼 것처럼 풀이를 작성하면 될 것 같다.

풀이

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

int N, M, rst;
int map[500][500];
int dx[] = { 0, -1, 0, 1, 1};
int dy[] = { 1, 0, -1, 0, 1 };

void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	rst = 0;
}

int is_range(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < M) return true;
	return false;
}

int one(int x, int y, int cnt) {
	const int case_num = 2;
	const int idx = 3;
	int vec[case_num][idx] = { {0, 0, 0}, {3, 3, 3} };
	int nx, ny, sum, rst = 0;
	bool flag;
	int xx = x, yy = y;
	
	for (int i = 0; i < case_num; i++) {
		flag = true;
		sum = cnt;
		x = xx, y = yy;
		for (int j = 0; j < idx; j++) {
			nx = x + dx[vec[i][j]];
			ny = y + dy[vec[i][j]];
			x = nx; y = ny;
			if (is_range(nx, ny)) {
				sum += map[nx][ny];
			}
			else {
				flag = false;
				break;
			}

		}
		if (flag) rst = max(sum, rst);
	}
	return rst; // 놓을 수 없는 경우 0을 리턴 근데 그럴 경우 없음
}

int two(int x, int y, int cnt) {
	const int case_num = 1;
	const int idx = 3;
	int vec[case_num][idx] = { {0, 3, 4} };

	int nx, ny, sum, rst = 0;
	bool flag;
	int xx = x, yy = y;
	for (int i = 0; i < case_num; i++) {

		flag = true;
		sum = cnt;
		x = xx, y = yy;
		for (int j = 0; j < idx; j++) {
			nx = x + dx[vec[i][j]];
			ny = y + dy[vec[i][j]];
			if (is_range(nx, ny)) {
				sum += map[nx][ny];
			}
			else {
				flag = false;
				break;
			}

		}
		if (flag) rst = max(sum, rst);
	} 
	return rst;

}

int three(int x, int y, int cnt) {
	const int case_num = 8;
	const int idx = 3;
	int vec[case_num][idx] = { {3,3,0}, {3,3,2}, {0,3,3}, {2,3,3}, {3,2,2}, {3, 0, 0}, {0, 0, 3}, {2, 2, 3} };

	int nx, ny, sum, rst = 0;
	bool flag;
	int xx = x, yy = y;
	for (int i = 0; i < case_num; i++) {
		flag = true;
		sum = cnt;
		x = xx, y = yy;
		for (int j = 0; j < idx; j++) {
			nx = x + dx[vec[i][j]];
			ny = y + dy[vec[i][j]];
			x = nx; y = ny;
			if (is_range(nx, ny)) {
				sum += map[nx][ny];
			}
			else {
				flag = false;
				break;
			}

		}
		if (flag) rst = max(sum, rst);
	}
	return rst;
}

int four(int x, int y, int cnt) {
	const int case_num = 4;
	const int idx = 3;
	int vec[case_num][idx] = { {3,0,3}, {3,2,3},{0,3,0},{2,3,2} };

	int nx, ny, sum, rst = 0;
	bool flag;
	int xx = x, yy = y;
	for (int i = 0; i < case_num; i++) {

		flag = true;
		sum = cnt;
		x = xx, y = yy;
		for (int j = 0; j < idx; j++) {
			nx = x + dx[vec[i][j]];
			ny = y + dy[vec[i][j]];
			x = nx; y = ny;
			if (is_range(nx, ny)) {
				sum += map[nx][ny];
			}
			else {
				flag = false;
				break;
			}

		}
		if (flag) rst = max(sum, rst);
	}
	return rst;
}
int five(int x, int y, int cnt) {
	const int case_num = 4;
	const int idx = 3;
	int vec[case_num][idx] = { {0,3,0}, {3,2,3}, {3,2,0},{3,0,3} };

	int nx, ny, sum, rst = 0;
	int px, py;
	bool flag;

	for (int i = 0; i < case_num; i++) {
		flag = true;
		sum = cnt;
		for (int j = 0; j < idx; j++) {
			if (j == 0) {
				nx = x + dx[vec[i][j]];
				ny = y + dy[vec[i][j]];
				px = nx; py = ny;
			}
			else {
				nx = px + dx[vec[i][j]];
				ny = py + dy[vec[i][j]];
			}
			if (is_range(nx, ny)) {
				sum += map[nx][ny];
			}
			else {
				flag = false;
				break;
			}
		}
		if (flag) rst = max(sum, rst);
	}
	return rst;
}

void test(int x, int y, int cnt) {
	rst = max(rst, one(x, y, cnt));
	rst = max(rst, two(x, y, cnt));
	rst = max(rst, three(x, y, cnt));
	rst = max(rst, four(x, y, cnt));
	rst = max(rst, five(x, y, cnt));

}

void solve() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			test(i, j, map[i][j]);
		}
	}
}

int main() {
	input();
	solve();
	cout << rst << endl;
}

찾아보니 DFS 문제라는데 나는 하드코딩으로 냅따 품.. 최적화란 없다.. 다시 풀어봐야겠다.