백준 15673: 감시 [C언어], 삼성 코딩 테스트

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

15683번: 감시

 

#include <stdio.h>
#define max(a, b) a < b ? b : a
using namespace std;
int y, x;
int dy[10] = {0, 1, 0, -1, 0, 1, 0, -1, 0};
int dx[10] = {0, 0, 1, 0, -1, 0, 1, 0, -1};
int map[11][11];
int view[11][11];
int camera[9][3];
int camnum;
int block;
void input();
int solve(int n, int cnt);
 
int main(){
    input();
    printf("%d ", y * x - solve(1, 0) - block);
    return 0;
}
 
void input() {
    scanf("%d %d", &y, &x);
    for (int i = 1; i <= y; i++) {
        for (int j = 1; j <= x; j++) {
            scanf("%d", map[i] + j);
            if (map[i][j]){
                block++;
                if (map[i][j] < 6) {
                    camera[++camnum][0] = map[i][j]; camera[camnum][1] = i; camera[camnum][2] = j;
                }
            }
        }
    }
}
 
int solve(int n, int cnt) {
    if (n == camnum + 1) return cnt;
    int ans = 0;
    int tmp = 0;
    if (camera[n][0] == 1) {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                if (view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]) {
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                    tmp++;
                }
            }
            ans = max(ans, solve(n + 1, cnt + tmp));
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]--;
            }
            tmp = 0;
        }
    }
    else if (camera[n][0] == 2) {
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                if (view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]){
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
                else{
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                    tmp++;
                }
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 2] * j > y or camera[n][1] + dy[i + 2] * j < 1 or camera[n][2] + dx[i + 2] * j > x or camera[n][2] + dx[i + 2] * j < 1) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] > 0 and map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] < 6) continue;
                if (view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]){
                    view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]++;
                    tmp++;
                }
            }
            ans = max(ans, solve(n + 1, cnt + tmp));
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]--;
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 2] * j > y or camera[n][1] + dy[i + 2] * j < 1 or camera[n][2] + dx[i + 2] * j > x or camera[n][2] + dx[i + 2] * j < 1) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] > 0 and map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] < 6) continue;
                view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]--;
            }
            tmp = 0;
        }
    }
    else if (camera[n][0] == 3) {
        for (int i = 1; i <= 3; i+=2) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                if (view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]) {
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
                else{
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                    tmp++;
                }
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 1] * j > y or camera[n][1] + dy[i + 1] * j < 1 or camera[n][2] + dx[i + 1] * j > x or camera[n][2] + dx[i + 1] * j < 1) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] > 0 and map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] < 6) continue;
                if (view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]) {
                    view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]++;
                    tmp++;
                }
            }
            ans = max(ans, solve(n + 1, cnt + tmp));
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]--;
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 1] * j > y or camera[n][1] + dy[i + 1] * j < 1 or camera[n][2] + dx[i + 1] * j > x or camera[n][2] + dx[i + 1] * j < 1) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] > 0 and map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] < 6) continue;
                view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]--;
            }
            tmp = 0;
        }
        
        tmp = 0;
        for (int i = 1; i <= 3; i+=2) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                if (view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]) {
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                    tmp++;
                }
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 3] * j > y or camera[n][1] + dy[i + 3] * j < 1 or camera[n][2] + dx[i + 3] * j > x or camera[n][2] + dx[i + 3] * j < 1) break;
                if (map[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j] > 0 and map[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j] < 6) continue;
                if (view[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j]) {
                    view[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j]++;
                    tmp++;
                }
            }
            ans = max(ans, solve(n + 1, cnt + tmp));
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]--;
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 3] * j > y or camera[n][1] + dy[i + 3] * j < 1 or
                    camera[n][2] + dx[i + 3] * j > x or camera[n][2] + dx[i + 3] * j < 1) break;
                if (map[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j] > 0 and
                    map[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j] < 6) continue;
                view[camera[n][1] + dy[i + 3] * j][camera[n][2] + dx[i + 3] * j]--;
                tmp++;
            }
            tmp = 0;
        }
    }
    else if (camera[n][0] == 4) {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                if (view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]) {
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
                else {
                    tmp++;
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 1] * j > y or camera[n][1] + dy[i + 1] * j < 1 or camera[n][2] + dx[i + 1] * j > x or camera[n][2] + dx[i + 1] * j < 1) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] > 0 and map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] < 6) continue;
                if (view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]){
                    view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]++;
                    tmp++;
                }
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 2] * j > y or camera[n][1] + dy[i + 2] * j < 1 or camera[n][2] + dx[i + 2] * j > x or camera[n][2] + dx[i + 2] * j < 1) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] > 0 and map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] < 6) continue;
                if (view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]){
                    view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]++;
                }
                else {
                    view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]++;
                    tmp++;
                }
            }
            ans = max(ans, solve(n + 1, cnt + tmp));
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]--;
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 1] * j > y or camera[n][1] + dy[i + 1] * j < 1 or camera[n][2] + dx[i + 1] * j > x or camera[n][2] + dx[i + 1] * j < 1) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] > 0 and map[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j] < 6) continue;
                view[camera[n][1] + dy[i + 1] * j][camera[n][2] + dx[i + 1] * j]--;
            }
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i + 2] * j > y or camera[n][1] + dy[i + 2] * j < 1 or camera[n][2] + dx[i + 2] * j > x or camera[n][2] + dx[i + 2] * j < 1) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] == 6) break;
                if (map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] > 0 and map[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j] < 6) continue;
                view[camera[n][1] + dy[i + 2] * j][camera[n][2] + dx[i + 2] * j]--;
            }
            tmp = 0;
        }
    }
    else {
        for(int i = 1; i <= 4; i++) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                if (view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]){
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                }
                else{
                    view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]++;
                    tmp++;
                }
            }
        }
        ans = max(ans, solve(n + 1, cnt + tmp));
        for(int i = 1; i <= 4; i++) {
            for (int j = 1; ; j++) {
                if (camera[n][1] + dy[i] * j > y or camera[n][1] + dy[i] * j < 1 or camera[n][2] + dx[i] * j > x or camera[n][2] + dx[i] * j < 1) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] == 6) break;
                if (map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] > 0 and map[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j] < 6) continue;
                view[camera[n][1] + dy[i] * j][camera[n][2] + dx[i] * j]--;
            }
        }
    }
    return ans;
}