A. 문제설명
https://www.acmicpc.net/problem/14500
문제에 대한 자세한 설명은 링크 참조
1. N * M 크기의 배열이 존재
2. 배열 위에 5개 종류의 테트리스 도형(테트로미노) 하나를 놓으려고 함
3. 테트로미노는 회전하거나 대칭시킬 수 있다.
4. 각 배열에 엔트리에 숫자 값이 존재하는 데 특정 위치에 이 테트로미노 하나를 놓아 최대의 합을 갖게 하는 경우 출력
B. 접근법
완전탐색과 시뮬레이션
먼저 이 문제에 대해 접근하려면 A. 문제설명의 3번 조건을 고려하여야 한다. 나의 경우 테트로미노의 4방향 회전과 대칭된 도형의 모양을 고려하여 구현하였고,
매 좌표를 탐사할 때 위와 같이 각각의 테트로미노 도형에 대해서 4방향을 회전한 경우의 영역의 엔트리 값의 합을 계산한다. 계산된 값이 최대일 때마다 전역의 값에 업데이트하는 방식이다.
C. 풀이
1. N*M 배열을 모두 탐사하며 각 좌표에 대해 놓을 수 있는 도형의 숫자 합을 구함
2. 도형의 모양은 아래와 같이 표현할 수 있다.
string shape[7] = {"000", "012", "100", "300", "010", "030", "004"};
2-1. 여기서 shape[2]/[3]과 shape[4]/[5]는 대칭된 모양의 같은 도형이다.
2-2. 도형의 모양은 각 좌표에서 이동하는 방향으로 표현할 수 있는데,
2-3. 0:→, 1:↓, 2:←, 3:↑, 4:↙, 5:↖, 6:↗, 7:↘를 의미한다.
3. 각 도형을 회전시키는 경우는 아래와 같이 표현할 수 있다.
string dir[7] = {"01", "0", "0123", "0123", "01", "01", "0123"};
3-1. 여기서 0:→, 1:↓, 2:←, 3:↑을 의미하고,
3-2. 각 도형별로 중복되는 회전의 경우는 제외했다.
4. 모양과 각도에 따라 배열내 숫자 값을 가져오게 되고 도형이 배열의 범위를 벗어나는 경우는 제외함
5. 완전 탐색하여 그 중 최대의 Sum 값을 반환
D. 내 코드
