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

https://www.acmicpc.net/problem/14500

14500번: 테트로미노

 

풀이

이 문제는 테트로미노들이 이미 주어져있고 그 개수가 별로 되지 않기 때문에 회전하거나 대칭을 시켰을 경우를 모두 구해놓았다. 그 경우들은 아래와 같다.

pair<int,int> tetris[19][4] = {{{0, 0}, {0, 1}, {0, 2}, {0, 3}},
                            {{0, 0}, {1, 0}, {2, 0}, {3, 0}}, 
                            {{0, 0}, {1, 0}, {0, 1}, {1, 1}},
                            {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
                            {{0, 0}, {0, 1}, {0, 2}, {-1, 2}},
                            {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
                            {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
                            {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
                            {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
                            {{0, 0}, {0, 1}, {1, 1}, {0, 2}},
                            {{0, 0}, {1, 0}, {1, 1}, {2, 0}}, 
                            {{0, 0}, {0, 1}, {-1, 1}, {0, 2}},
                            {{0, 0}, {0, 1}, {-1, 1}, {1, 1}},
                            {{0, 0}, {0, 1}, {-1, 1}, {-2, 1}},
                            {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
                            {{0, 0}, {0, 1}, {1, 0}, {2, 0}},
                            {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
                            {{0, 0}, {1, 0}, {1, -1}, {2, -1}},
                            {{0, 0}, {0, 1}, {1, 1}, {1, 2}}};

위의 그림에서 나올 수 있는 경우의 수는

• 민트색의 경우 90도 회전하는 경우만 다르므로 만들 수 있는 경우의 수가 2가지
• 노랑색의 경우 회전, 대칭 모두 같은 모양이므로 1가지
• 주황생의 경우 90도 회전할때마다 다르고 대칭해서도 90도 회전할 때마다 다르므로 8가지
• 연두색의 경우 90도로 회전할 경우 1가지, 대칭시킬 경우 1가지, 대칭시켜서 90도 회전할 경우 1가지로 총 4가지
• 보라색의 경우 대칭할 경우 똑같고 회전시킬 경우로 총 4가지

합치면 모두 19가지의 경우의 수가 존재한다. 위의 코드는 각각 이루는 네 가지 칸의 좌표들을 적은 것이다. 코드는 아래와 같이 동작한다.

1. NxM 크기의 종이의 모든 점을 시작점으로 하여 위 19가지의 도형을 종이 위에 그린다.
2. 시작점은 (0, 0)이다.
3. 테트로미노를 구성하는 4가지 칸 중에 한 칸이라도 종이를 벗어날 경우는 제외한다.
4. 벗어나는 경우가 없을 경우 테트로미노가 올라가 있는 칸에 적혀있는 수의 합을 구한다.
5. 최대값을 갱신한다.

코드로 작성할 경우 다음과 같다.

 

소스 코드

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

using namespace std;

int arr[501][501]; //종이
//19가지 도형
pair<int,int> tetris[19][4] = {{{0, 0}, {0, 1}, {0, 2}, {0, 3}}, 
                            {{0, 0}, {1, 0}, {2, 0}, {3, 0}}, 
                            {{0, 0}, {1, 0}, {0, 1}, {1, 1}},
                            {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
                            {{0, 0}, {0, 1}, {0, 2}, {-1, 2}},
                            {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
                            {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
                            {{0, 0}, {1, 0}, {1, 1}, {2, 1}},
                            {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
                            {{0, 0}, {0, 1}, {1, 1}, {0, 2}},
                            {{0, 0}, {1, 0}, {1, 1}, {2, 0}}, 
                            {{0, 0}, {0, 1}, {-1, 1}, {0, 2}},
                            {{0, 0}, {0, 1}, {-1, 1}, {1, 1}},
                            {{0, 0}, {0, 1}, {-1, 1}, {-2, 1}},
                            {{0, 0}, {1, 0}, {1, 1}, {1, 2}},
                            {{0, 0}, {0, 1}, {1, 0}, {2, 0}},
                            {{0, 0}, {0, 1}, {0, 2}, {1, 2}},
                            {{0, 0}, {1, 0}, {1, -1}, {2, -1}},
                            {{0, 0}, {0, 1}, {1, 1}, {1, 2}}};
int main() {
    int N, M; cin >> N >> M;
    int ans = 0;
    for(int i = 0 ; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> arr[i][j]; //종이에 적혀있는 수 입력
        }
    }
    pair<int,int> board[4]; //하나의 테트로미노를 구성하는 배열
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int d = 0; d < 19; d++) { //19가지 도형에 대해
                bool chk = false; //종이를 벗어나는지 여부 체크
                for(int k = 0; k < 4; k++) { //4가지 칸에 대하여
                    board[k] = tetris[d][k]; //d번째 도형의 k번째 위치 저장
                    board[k].first += i, board[k].second += j; //(i, j)부터 시작했으므로 x, y좌표에 각각 더해줌
                    if(board[k].first < 0 || board[k].first >= N || board[k].second < 0 || board[k].second >= M) { 
			//종이를 벗어나는 경우
                        chk = true; //벗어났다고 표시 후
                        break; //벗어남
                    }
                }
                if(!chk) { //종이를 벗어나지 않은 경우
                    int sum = 0;
                    for(int k = 0; k < 4; k++) { //테트로미노가 올려져 있는 위치의 수의 합 계산
                        sum += arr[board[k].first][board[k].second];
                    }
                    ans = max(ans, sum); //최대값 갱신
                }
            }
        }
    }
    cout << ans;
}

위 코드는 풀이대로 작성한 코드이다. 만약 테트로미노가 많고 예측할 수 없다면 이런 방식을 사용할 수 없지만 정해져있는 값이기 때문에 더 빠른 계산을 위해 위의 방식으로 풀었다. 이런 방식을 사용하지 못할 경우 대칭, 회전하는 함수를 만들었어야할 것이다.

 

채점 결과