[삼성코테기출문제] 테트로미노

테트로미노

문제

지도 위에 테트로미노의 모양의 틀을 만들어 계산하자! 라는 생각이 들었다. 테트로미노는 4개의 정사각형을 이어 붙여 만들 수 있는 모든 모양이라 처음에는 DFS를 이용해서 모든 모양을 만들 수 있지 않을까? 라는 생각이 들었다. 하지만 구현 과정에서 ㅗ 모양은 만들 수 없다는 것을 깨닳았다. 이미 다 구현된 상태에서 다시 작성하려니… 앞이 깜깜했다. 실제 시험에서 이렇게 잘못된방향으로 코딩을하게 된다면…… 끔찍하다.
하지만 위의 방법으로 구현한 친구가 있다. 같이 알고리즘 공부하는 동생인데, ㅗ모양의 합을 구하는 과정이 매우 인상깊었다.
[u_story] 2019.10.08 _ SW 역량 테스트 기출 문제(day-03)

문제 풀이

입출력 조건

생각의 생각 끝에 내린 결론은 모든 테트로미노를 만들어 놓고 문제를 풀어야겠다고 생각했다. 뭔가 마음에 안들지만… 이전에 풀었던 주사위 굴리기에서 했던 것 처럼…
현재 위치를 기준으로 모양을 만들어 주었다.

이유는 모르겠는데 마크다운 오류때문에 아래와 같이 표기했다…

Pos Tetromino[19][4] =
{
	\{\{0,0\},\{0,1\},\{1,0\},\{1,1\}\},	//ㅁ
	\{\{0,0\},\{1,0\},\{2,0\},\{3,0\}\},	//ㅡ ㅣ
	\{\{0,0\},\{0,1\},\{0,2\},\{0,3\}\},
	\{\{0,1\},\{1,1\},\{2,1\},\{1,0\}\},	//ㅗ ㅜ ㅓ ㅏ
	\{\{0,0\},\{1,0\},\{2,0\},\{1,1\}\},
	\{\{0,1\},\{1,0\},\{1,1\},\{1,2\}\},
	\{\{0,0\},\{0,1\},\{0,2\},\{1,1\}\},
	\{\{0,0\},\{1,0\},\{1,1\},\{2,1\}\},	//z
	\{\{1,0\},\{1,1\},\{0,1\},\{0,2\}\},
	\{\{0,1\},\{1,1\},\{1,0\},\{2,0\}\},
	\{\{0,0\},\{0,1\},\{1,1\},\{1,2\}\},
	\{\{0,0\},\{1,0\},\{2,0\},\{2,1\}\},	//ㄱ ㄴ
	\{\{0,0\},\{0,1\},\{0,2\},\{1,0\}\},
	\{\{0,0\},\{0,1\},\{1,1\},\{2,1\}\},
	\{\{0,2\},\{1,2\},\{1,1\},\{1,0\}\},
	\{\{0,0\},\{1,0\},\{2,0\},\{0,1\}\},
	\{\{0,0\},\{0,1\},\{0,2\},\{1,2\}\},
	\{\{0,1\},\{1,1\},\{2,1\},\{2,0\}\},
	\{\{0,0\},\{1,0\},\{1,1\},\{1,2\}\}
};

막상 만들어 놓고 문제를 푸니 나머지 로직은 금방금방 구현되었다.

풀이 과정

1. 입력받은 N x M번 모두 시행한다. (0,0) ~ (M-1,N-1)
2. 해당 좌표를 기준으로 19개의 테트로미노 모양 안의 숫자들의 합을 구한다.
3. 만약 범위를 벗어난다면 break를 걸어준다.
4. 모두 더한 sum의 값이 최대값인지 확인 후 위의 과정을 반복한다.

#include<iostream>
using namespace std;
const int MAX = 500;

int N, M, Max;
int Map[MAX][MAX];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,-1,1 };
typedef struct Pos {
	int x, y;
};
Pos Tetromino[19][4] =
{
	\{\{0,0\},\{0,1\},\{1,0\},\{1,1\}\},	//ㅁ
	\{\{0,0\},\{1,0\},\{2,0\},\{3,0\}\},	//ㅡ ㅣ
	\{\{0,0\},\{0,1\},\{0,2\},\{0,3\}\},
	\{\{0,1\},\{1,1\},\{2,1\},\{1,0\}\},	//ㅗ ㅜ ㅓ ㅏ
	\{\{0,0\},\{1,0\},\{2,0\},\{1,1\}\},
	\{\{0,1\},\{1,0\},\{1,1\},\{1,2\}\},
	\{\{0,0\},\{0,1\},\{0,2\},\{1,1\}\},
	\{\{0,0\},\{1,0\},\{1,1\},\{2,1\}\},	//z
	\{\{1,0\},\{1,1\},\{0,1\},\{0,2\}\},
	\{\{0,1\},\{1,1\},\{1,0\},\{2,0\}\},
	\{\{0,0\},\{0,1\},\{1,1\},\{1,2\}\},
	\{\{0,0\},\{1,0\},\{2,0\},\{2,1\}\},	//ㄱ ㄴ
	\{\{0,0\},\{0,1\},\{0,2\},\{1,0\}\},
	\{\{0,0\},\{0,1\},\{1,1\},\{2,1\}\},
	\{\{0,2\},\{1,2\},\{1,1\},\{1,0\}\},
	\{\{0,0\},\{1,0\},\{2,0\},\{0,1\}\},
	\{\{0,0\},\{0,1\},\{0,2\},\{1,2\}\},
	\{\{0,1\},\{1,1\},\{2,1\},\{2,0\}\},
	\{\{0,0\},\{1,0\},\{1,1\},\{1,2\}\}
};
void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> Map[i][j];
}
void Process(int x, int y) {
	Pos cur = { x,y };
	for (int i = 0; i < 19; i++) {
		int sum = 0;
		for (int j = 0; j < 4; j++) {
			int nx = cur.x + Tetromino[i][j].x;
			int ny = cur.y + Tetromino[i][j].y;
			if (nx >= 0 && ny >= 0 && nx < M&&ny < N) {
				sum += Map[ny][nx];
			}
			else break;
			if (Max < sum)Max = sum;
		}
	}
}
void Solution() {
	Input();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			Process(j, i);
		}
	}
	cout << Max << endl;
}
int main() {
	freopen("06.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}