18430번 무기 공학

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

# 탐색 # dfs # 복습 # 구현 # 브루트포스 # 추천 # 코딩 # 코테 # 백트래킹 # back

백트래킹 문제이다.

현재 좌표에서 방문하는 경우, 방문하지 않는 경우까지 모두 고려해준다.

나머지는 주석 참고

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 6
 
// 각 좌표를 곱셈으로 활용할 것임
vector<vector<vector<int> > > v = {
    {
        { 1, 2 },
        { 0, 1 }
    },
    {
        { 0, 1 },
        { 1, 2 }
    },
    {
        { 1, 0 },
        { 2, 1 }
    },
    {
        { 2, 1 },
        { 1, 0 }
    },
};
 
int R, C, m[Max][Max], ans;
bool use[Max][Max]; // 방문했는지 여부
 
// 범위와 이미 방문했는지 검사
bool chk(int r, int c, int number)
{
    if (r == R - 1 || c == C - 1) {
        return false;
    }
 
    if (number == 0) {
        if (use[r][c] || use[r][c + 1] || use[r + 1][c + 1]) {
            return false;
        }
    }
    else if (number == 1) {
        if (use[r][c + 1] || use[r + 1][c + 1] || use[r + 1][c]) {
            return false;
        }
    }
    else if (number == 2) {
        if (use[r][c] || use[r + 1][c] || use[r + 1][c + 1]) {
            return false;
        }
    }
    else if (number == 3) {
        if (use[r][c] || use[r][c + 1] || use[r + 1][c]) {
            return false;
        }
    }
 
    return true;
}
 
int draw(int r, int c, int number, bool b)
{
    if (number == 0) {
        use[r][c] = use[r][c + 1] = use[r + 1][c + 1] = b;
    }
    else if (number == 1) {
        use[r][c + 1] = use[r + 1][c + 1] = use[r + 1][c] = b;
    }
    else if (number == 2) {
        use[r][c] = use[r + 1][c] = use[r + 1][c + 1] = b;
    }
    else if (number == 3) {
        use[r][c] = use[r][c + 1] = use[r + 1][c] = b;
    }
 
    return 
        m[r][c]         * v[number][0][0] + 
        m[r][c + 1]     * v[number][0][1] + 
        m[r + 1][c]     * v[number][1][0] + 
        m[r + 1][c + 1] * v[number][1][1];
}
 
void dfs(int r, int c, int total)
{
    if (c == C - 1) {
        ++r;
        c = 0;
    }
 
    if (r == R - 1) {
        ans = max(ans, total);
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (chk(r, c, i)) {
            // 방문하고 넘어가는 경우
            int score = draw(r, c, i, true);
            dfs(r, c + 1, total + score);
            draw(r, c, i, false);
        }
    }
 
    // 방문하지 않고, 그냥 다음으로 넘어가는 경우
    dfs(r, c + 1, total);
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d", &R, &C);
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
        }
    }
 
    // 2 x 2 사각형을 만들 수 없는 경우
    if (R == 1 || C == 1) {
        printf("0\n");
        return 0;
    }
 
    dfs(0, 0, 0);
 
    printf("%d\n", ans);
    
    return 0;
}