테트로미노_14500

문제출처 : 테트로미노_14500

파라미터 정리

N,M : 주어진 필드의 크기
Map[N][M] : 각 칸의 값
출력값: 테트로미노 내부 합산의 최대값

간략한 과정

5가지 도형에 대한 dr, dc 정의하기
모든 경우에 대해 한번씩 실행한 후 최대값 반환하기

코드

stack 구현

#include <iostream>
#include <algorithm>

using namespace std;

int N,M;
int input[500][500];
bool visit[500][500] = {false,};
int answer = 0;

typedef struct point{
    int x, y;
} point;

//stack 정의
point STACK[5];
int top = -1;

point pop() {
    return STACK[top--];
}

void push(int x,int y){
    STACK[++top].x = x;
    STACK[top].y = y;
} 

//상하좌우
int dArr[][4] = { {0,1}, {0,-1}, {1,0}, {-1,0} };

void dfs(int n, int m, int sum, int depth){
    sum += input[n][m];
    
    if(depth == 1){
        answer = max(answer, sum);
        return;
    }
    
    push(n,m);
    visit[n][m] = true;
    
    for(int i = 0; i < top+1; i++){
        for(int j = 0; j < 4; j++){
            int nr = STACK[i].x + dArr[j][0];
            int nc = STACK[i].y + dArr[j][1];
            
            if(nr<0 || nc<0 || nr > N-1 || nc > M-1) continue;
            
            if(!visit[nr][nc]){
                dfs(nr, nc, sum, depth-1);
            }
        }
    }
    
    visit[n][m] = false;
    pop();
    
    return;
}

int main()
{
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> input[i][j];
        }
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            dfs(i, j, 0, 4);
        }
    }
    
    cout << answer << endl;

    return 0;
}

다른 풀이

vector 사용

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

using namespace std;

struct loc{
    int r,c; 
};

int N,M;
int map[500][500];
bool visit[500][500] = {false,};
vector<loc> list;
int res = 0;

int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void move(int r, int c, int sum, int dis){
    sum += map[r][c];
    
    if(dis == 4){
        res = max(res, sum);
        return;
    }
    
    list.push_back({r,c});
    visit[r][c] = true;
    
    for(int i = 0; i < list.size(); i++){
        for(int d = 0; d < 4; d++){
            int nr = list[i].r + dr[d];
            int nc = list[i].c + dc[d];
            
            if(nr < 0 || nc < 0 || nr > N-1 || nc > M-1) continue;
            if(visit[nr][nc]) continue;
            
            move(nr, nc, sum, dis+1);
        }
    }
    
    visit[r][c] = false;
    list.pop_back();
    
    return;
}

int solve(){
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            move(i,j,0,1);
        }
    }
    
    return res;
}

int main()
{
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> map[i][j];
        }
    }

    cout << solve() << endl;

    return 0;
}

시행착오

#include <iostream>
#include <algorithm>

using namespace std;

int N,M;
int Map[500][500];
int onceBlock[2][4] = {
    {0,1,0,1}, {0,0,1,1}
};
int twiceBlock[12][4] = {
    {0,0,0,0}, {0,1,2,3},
    {0,1,2,1}, {0,0,0,1},
    {0,1,2,1}, {0,0,0,-1},
    {0,0,1,1}, {0,1,1,2},
    {0,0,0,1}, {0,1,2,2},
    {0,0,0,-1}, {0,1,2,2}
};

int calculateSum(int dr[4], int dc[4]){
    int res = 0;
    int sum = 0;
    bool flag = true;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            for(int k = 0; k < 4; k++){
                int nr = i + dr[k];
                int nc = j + dc[k];
                
                if(nr < 0 || nc < 0 || nr > N-1 || nc > M-1){
                    flag = false;
                    continue;
                }
                
                sum += Map[nr][nc];
            }
            
            if(flag)
                res = max(res,sum);
                
            flag =true;
            sum = 0;
        }
    }
    
    return res;
}

int solve(){
    int res = 0;
    int currentSum = 0;
    
    res = max(res, calculateSum(onceBlock[0], onceBlock[1]));
    
    for(int i = 0; i < 6; i++){
        res = max(res, calculateSum(twiceBlock[(i*2)], twiceBlock[(i*2)+1]));
        res = max(res, calculateSum(twiceBlock[(i*2)+1], twiceBlock[(i*2)]));
    }
    
    return res;
}

int main()
{
    cin >> N >> M;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
        }
    }
    
    cout << solve() << endl;
    
    return 0;
}