BOJ - 14500번 테트로미노(C++)

문제 출처: https://www.acmicpc.net/problem/14500

문제 난이도

Gold 5

문제 접근법

N,M 숫자 범위가 작기 때문에 삼중 포문을 돌렸다.
테트로미노 경우의 수도 작기 때문에 함수를 두어 여러번 호출했다.
대신 ㅁ, ㅡ, ㄴ, ㄴㄱ 는 한붓그리기가 가능하다. 그러나 ㅗ는 한점에서 시작해서 한 붓그리기가 되지 않아 이 경우만 따로 만들어서 계산했다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int dy[4][2] = { {-1,0},{1,0}, {0,1},{0,-1} }; //위,아래,오,왼,대각선
int cross[3][2] = { {1,1}, {1,-1},{-1,1} }; 
int arr[501][501];
int res = -1;
int N, M;

void checkBox(vector<int> a) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int sum = arr[i][j];
			bool flag = true;
			int x = i, y = j;
			for (int k = 0; k < a.size(); k++) {
				int nx = x + dy[a[k]][0];
				int ny = y + dy[a[k]][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
					flag = false;
					break;
				}
				sum += arr[nx][ny];
				x = nx;
				y = ny;
			}
			if (flag && res < sum) res = sum;
		}
	}
}

void checkOther(vector<int> a, int crossIdx) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int sum = arr[i][j];
			bool flag = true;
			int x = i, y = j;
			if (i + cross[crossIdx][0] < 0 || i + cross[crossIdx][0] >= N || j + cross[crossIdx][1] < 0 || j + cross[crossIdx][1] >= M) continue;
			sum += arr[i + cross[crossIdx][0]][j + cross[crossIdx][1]];
			for (int k = 0; k < a.size(); k++) {
				int nx = x + dy[a[k]][0];
				int ny = y + dy[a[k]][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
					flag = false;
					break;
				}
				sum += arr[nx][ny];
				x = nx;
				y = ny;
			}
			if (flag && res < sum) res = sum;
		}
	}
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> arr[i][j];
		}
	}

	//ㅁ
	checkBox({ 1,2,0 }); //아래,오른쪽,위

	//ㅡ
	checkBox({ 2,2,2 }); //오른
	checkBox({ 1,1,1 }); //아래

	//ㄴ
	checkBox({ 1,1,2 });
	checkBox({ 0,2,2 });
	checkBox({ 2,1,1 });
	checkBox({ 2,2,0 });

	//ㄴ 추가
	checkBox({ 2,0,0 });
	checkBox({ 0,0,2 });
	checkBox({ 1,2,2 });
	checkBox({ 2,2,1 });

	//ㄴㄱ
	checkBox({ 1,2,1 });
	checkBox({ 2,0,2 });
	checkBox({ 0,2,0 });
	checkBox({ 2,1,2 });

	//ㅗ
	checkOther({ 2,2 },0); //오른
	checkOther({ 2,2 }, 2); //오른
	checkOther({ 1,1 }, 1); //아래
	checkOther({ 1,1 }, 0); //아래

	cout << res << "\n";
	return 0;
}

피드백

이 문제를 구현하고 13%에서 틀려서 반례케이스를 질문 검색란에서 도움받아 실수를 찾았다.
1. ㅁ 부분을 한붓그리기로 실행하는데 갑자기 대각선으로 뻗어 ㅁ이 만들어지지 않았다.
2. ㄴ 모양은 총 8가지가 나온다. 회전, 대칭까지 해서 -> 난 4가지만 체크해줘서 그렇다.

만약 시험 도중이었다면 찾기 어려웠을 것 같다... 반례케이스 덕분에 찾은 경우라 ㅠ 생각 좀 꼼꼼히 해야겠다 제발!