[백준 14500] 테트로미노(C++)

📕문제

---

폴리오미노란 크기가 1 ×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1 ×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

📕입력

---

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

📕출력

---

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

 

🔎문제해석

---

나는 모든 경우의 수를 구해서 문제를 해결했지만, 문제를 다 풀고 다른 사람들은 어떻게 풀었는지 궁금해서 구글링을 해봤는데 dfs 등 탐색으로 푸는 풀이를 보고 아직 멀었구나 라는 것을 느꼈다..ㅠ나는 모든 좌표에 대해서 만들 수 있는 도형의 경우의 수를 대입해서 최댓값을 구했다.
if문을 덕지덕지 사용했지만, 생각해보면 if문 수를 덜 쓰고도 풀 수 있을 것 같긴 하다. 내가 못해서 그럼.

 

아래 그림은 테트로미노의 5가지 모양이다. 이 모양을 대칭, 회전을 시켜도 상관없다.

 

💡1번 도형으로 만들 수 있는 도형의 종류는 2가지다.

세로로 4개를 이어 붙인 모양과 가로로 4개를 이어 붙인 모양이다.

 

💡2번 도형으로 만들 수 있는 도형의 종류는 1가지다.

💡3번 도형으로 만들 수 있는 도형의 종류는 8가지다.

근데 여기서 만들수 있는 모양과 5번을 살짝 겹쳐서 본다면 툭 뒤 나온 부분을 조금만 수정하면 5번의 모양을 만들어낼 수 있다는 사실을 알 수 있다. 그러한 것을 반복문을 통해서 나는 5번과 3번을 같이 묶어서 처리했다.

 

💡4번 도형으로 만들 수 있는 도형의 종류는 4가지다.

각 종류마다 예외처리를 해서 4개의 경우의 수를 구했다.

 

이렇게 한 좌표에 대해서 모든 도형의 값을 구했고, 그것을 모든 좌표로 확대하면 N * M 행렬에 대해서  테트로미노로 구할 수 있는 최댓값을 구할 수 있다.

---

💻코드

/*
백준 골드4 테트로미노
사각형의 형태는 5개고 회전,대칭 가능

*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,sum=0,big=0;
vector<vector<int>>graph;
int main(){
    cin>>n>>m;
    graph.resize(n,vector<int>(m,0));
    for(int i=0; i<n;i++){
        for(int j=0; j<m;j++){
            cin>>graph[i][j];
        }
    }
    //모든 칸에 대해서 만들 수 있는 모든 사각형을 넣어보기?
    for(int i=0; i<n;i++){
        for(int j=0; j<m;j++){
            //항상 graph[i][j]가 있어야함.
            if(i+3<n){ //세로로 4개 이어붙인거
                sum=graph[i][j]+graph[i+1][j]+graph[i+2][j]+graph[i+3][j];
                if(sum>big){
                    big=sum;
                }
            }
            if(j+3<m){ //가로로 4개 이어붙인거
                sum=graph[i][j]+graph[i][j+1]+graph[i][j+2]+graph[i][j+3];
                if(sum>big){
                    big=sum;
                }
            }
            if(i+1<n && j+1<m){ //2*2 정사각형 
                sum=graph[i][j]+graph[i+1][j]+graph[i][j+1]+graph[i+1][j+1];
                if(sum>big){
                    big=sum;
                }
            }
            if(i+2<n&& j+1<m){ //세로로  3개 이어 붙이고 가로로  오른쪽 하나씩 이어붙일 경우
                for(int k=0;k<3;k++){
                    if(sum<graph[i][j]+graph[i+1][j]+graph[i+2][j]+graph[i+k][j+1])
                    {
                        sum=graph[i][j]+graph[i+1][j]+graph[i+2][j]+graph[i+k][j+1];
                    }
                }
                if(sum>big){
                    big=sum;
                }
                            
            }
            if(i+2<n && j-1>=0){ //세로로 3개 이어붙이고 가로 왼쪽에 하나 붙이기.
                for(int k=0; k<3; k++){
                    if(sum<graph[i][j]+graph[i+1][j]+graph[i+2][j]+graph[i+k][j-1])
                    {
                        sum=graph[i][j]+graph[i+1][j]+graph[i+2][j]+graph[i+k][j-1];
                    }
                }
                if(sum>big){
                    big=sum;
                }
            }
            if(j+2<m && i+1<n){ //가로로 3개 이어붙이고 아래로 세로 1개 붙이는 경우.
                for(int k=0; k<3;k++){
                    if(sum<graph[i][j]+graph[i][j+1]+graph[i][j+2]+graph[i+1][j+k])
                    {
                        sum=graph[i][j]+graph[i][j+1]+graph[i][j+2]+graph[i+1][j+k];
                    }
                }
                if(sum>big){
                    big=sum;
                }
            }
            if(j+2<m && i-1>=0){ //가로로 3개 이어붙이고 아래로 세로 1개 붙이는 경우.
                for(int k=0; k<3;k++){
                    if(sum<graph[i][j]+graph[i][j+1]+graph[i][j+2]+graph[i-1][j+k])
                    {
                        sum=graph[i][j]+graph[i][j+1]+graph[i][j+2]+graph[i-1][j+k];
                    }
                }
                if(sum>big){
                    big=sum;
                }
            }
            //엇갈려서 2개 붙이는 경우. 총 4가지의 모형이 발견됨.
            if(i+2<n &&j+1<m) 
            {
                sum=graph[i][j]+graph[i+1][j]+graph[i+1][j+1]+graph[i+2][j+1];
                if(sum>big){
                    big=sum;
                }
            }
            if(i+1<n && j-1 >=0 && j+1<m)
            {
                sum=graph[i][j]+graph[i][j+1]+graph[i+1][j-1]+graph[i+1][j];
                if(sum>big){
                    big=sum;
                }
            }
            if(j-1>=0 && i+1 <n && j+1<m)
            {
                sum=graph[i][j]+graph[i][j-1]+graph[i+1][j]+graph[i+1][j+1];
                if(sum>big){
                    big=sum;
                }
            }
            if(i-1>=0 && j+1<m && i+1 <n){
                sum=graph[i][j]+graph[i+1][j]+graph[i][j+1]+graph[i-1][j+1];
                if(sum>big){
                    big=sum;
                }
            }
        }
    }
    cout<<big; //최대값 출력.
}

✔느낀 점

• 그냥 단순한 구현 문제로 생각해서 풀었기에 쉬웠다. 
• DFS를 사용한 풀이가 있다는 것이 충격이었다.