18430번 무기 공학

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

 

지난 번 풀이 : https://hsdevelopment.tistory.com/788

 

현재 좌표(r, c)를 부메랑으로 사용할지 말지 2가지의 경우를 모두 고려해야한다.

 

go bool 변수를 활용해서 현재 좌표(r, c)에서의 4가지 부메랑 중 하나를 수행했다고 해서,

현재 좌표(r, c)에서는 부메랑을 사용하지 않는 경우를 잊어버리며 안 된다.

오답인 소스코드는 현재 좌표(r, c)를 부메랑으로 사용한 후에는 go bool 변수에 true로 표시하는 바람에 그 밑의 경우(현재 좌표를 부메랑으로 사용하지 않을 때)가 수행되지 않는다. 

 

그래서, 단순 go bool 변수를 사용하지 않고, 삼중 for문 밑에 바로 simulation(r, c+1);만 두면, 1번 때문에 바로 시간 초과가 발생한다.

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 10

int R, C, ans = 0;
int m[MAX][MAX];
bool used[MAX][MAX];

bool chk(int number, int r, int c) {

    if (used[r][c]) return false;

    if (number == 1) {
        if (r + 1 >= R || c - 1 < 0 || used[r][c - 1] || used[r + 1][c]) return false;
    }
    else if (number == 2) {
        if (r - 1 < 0 || c - 1 < 0 || used[r][c - 1] || used[r - 1][c]) return false;
    }
    else if (number == 3) {
        if (r - 1 < 0 || c + 1 >= C || used[r][c + 1] || used[r - 1][c]) return false;
    }
    else if (number == 4) {
        if (r + 1 >= R || c + 1 >= C || used[r][c + 1] || used[r + 1][c]) return false;
    }

    return true;
}

int draw(int number, int r, int c, bool tf) {

    int sum = 0;
   
    used[r][c] = tf;
    sum += 2 * m[r][c];

    if (number == 1) {
        used[r][c - 1] = tf;
        used[r + 1][c] = tf;
        sum += m[r][c - 1];
        sum += m[r + 1][c];
    }
    else if (number == 2) {
        used[r][c - 1] = tf;
        used[r - 1][c] = tf;
        sum += m[r][c - 1];
        sum += m[r - 1][c];
    }
    else if (number == 3) {
        used[r][c + 1] = tf;
        used[r - 1][c] = tf;
        sum += m[r][c + 1];
        sum += m[r - 1][c];
    }
    else if (number == 4) {
        used[r][c + 1] = tf;
        used[r + 1][c] = tf;
        sum += m[r][c + 1];
        sum += m[r + 1][c];
    }

    return sum;
}

void simulation(int r, int c, int sum) {

    if (c == C) {
        ++r;
        c = 0;
    }

    if (r == R) {
        ans = max(ans, sum);
        return;
    }

    //bool go = false;

    for (int i = 1; i <= 4; i++) {
        if (chk(i, r, c)) {
            //go = true;
            sum += draw(i, r, c, true);
            simulation(r, c + 1, sum);
            sum -= draw(i, r, c, false);
        }
    }

    //if (!go) {
        simulation(r, c + 1, sum);
    //}
}

int main()
{
    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
        }
    }

    simulation(0, 0, 0);

    printf("%d\n", ans);

    return 0;
}