백준 14500 - 테트로미노

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

14500번: 테트로미노

문제 설명

---

아래의 그림처럼 4개의 정사각형이 연결되어(면이 닿아있다는 의미)있다면, 이 3개의 도형을 테트로미노라고 부른다. 이때 N*M의 메트릭스가 주어질때(각각의 메트릭스에는 하나의 작은 정사각형마다 숫자 크기가 적혀있다), 테트로미노 안의 숫자의 합이 가장 큰 숫자가 되게 하는 값을 구하는 문제이다~

 

접근 방식

 

---

일단 정말 완전탐색에 의미에 입각해서 모든 도형을 회전시킬 수 있는 모든방향으로 회전시킨 모형과,

대칭시킬 수 있는 모든 방향으로 대칭시킨 모형을 하나하나 다 대입해서 풀어도 답이 나온다고 한다.

저는 처음에 위에 말했던 방식으로 진행했다가 실패하고 다른 방법을 참고했습니다.

하지만, 모형들을 잘보면 공통점을 하나 발견할 수 있다.

바로 Depth = 3 이라는 것이다(***)

Depth가 나왔다는 건  DFS로의 접근이 가능하다!!!!

 

 

 

코드

---

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

const int MAX = 501;

int n,m;
int mat[MAX][MAX];
bool visit[MAX][MAX];

typedef struct{
    int y,x;
}Dir;

Dir moveDir[4]={{1,0},{-1,0},{0,1},{0,-1}};

int dfs(int y,int x,int cnt){	//DFS
    if(cnt==4){	//Depth==4가 되면 stop
        return mat[y][x];
    }
    int sum=0;
    for(int i=0;i<4;i++){
        int ny = y+ moveDir[i].y;
        int nx = x +moveDir[i].x;
        if(0<=ny&& ny<n&& 0<=nx&&nx<m && !visit[ny][nx]){
            visit[ny][nx]=true;
            sum=max(sum,mat[y][x]+ dfs(ny,nx,cnt+1));
            visit[ny][nx]=false;
        }
    }
    return sum;
}
int fxxx(int y, int x){
    int result = 0;
    //ㅗ 좌표의 중심을 가운데로 설정한다.
    if (y >= 1 && x >= 1 && x < m-1)
        result = max(result, mat[y][x-1]+mat[y][x]+mat[y-1][x]+mat[y][x+1]);
    //ㅏ 
    if (y >= 1 && y<n-1 && x<m-1)
        result = max(result, mat[y-1][x]+mat[y][x]+mat[y][x+1]+mat[y+1][x]);
    //ㅜ
    if (y >= 0 && y < n-1 && x <m-1)
        result = max(result, mat[y][x-1]+mat[y][x]+mat[y+1][x]+mat[y][x+1]);
    //ㅓ 
    if (y >= 1 && y <n-1 && x>= 1)
        result = max(result, mat[y-1][x]+mat[y][x]+mat[y][x-1]+mat[y+1][x]);
    return result;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mat[i][j];
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            visit[i][j]=true;
            ans=max(ans,dfs(i,j,1));
            ans=max(ans,fxxx(i,j));
            visit[i][j]=false;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

 

funny algorithm~:0