[알고리즘] 감시

• 포인트
• 방향을 전부 구할 수 있는가 (재귀 적으로 구하면 된다.)
• (입력) -> (모든 cctv 방향을 설정해준다.) ->(맵을 복사해서) ->(계산)
• 구현 방법은 정말 다양하게 작성할 수 있을 것 같습니다. 저는 재귀로 각각의 방향을 설정을 해주고 재귀를 작성을 하여서 맵을 표시하면서 어떻게 진행을 해야 하는지를 보는 것 같습니다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<vector>
#include <cstring>

#define endl "\n"
#define MAX 8
using namespace std;

int n, m, num, answer;
int map[MAX][MAX];
int cmap[MAX][MAX];

typedef struct {
    int x;
    int y;
    int type;
    int direction;
} machine;

vector<machine> cctv;

void Right(int x, int y) {
    for (int i = y + 1; i < m; i++) {
        if (cmap[x][i] == 6) break;
        if (1 <= cmap[x][i] && cmap[x][i] <= 5) continue;
        cmap[x][i] = -1;
    }
}

void Left(int x, int y) {
    for (int i = y - 1; i >= 0; i--) {
        if (cmap[x][i] == 6) break;
        if (1 <= cmap[x][i] && cmap[x][i] <= 5) continue;
        cmap[x][i] = -1;
    }
}

void Down(int x, int y) {
    for (int i = x + 1; i < n; i++) {
        if (cmap[i][y] == 6) break;
        if (1 <= cmap[i][y] && cmap[i][y] <= 5) continue;

        cmap[i][y] = -1;
    }
}

void Up(int x, int y) {
    for (int i = x - 1; i >= 0; i--) {
        if (cmap[i][y] == 6) break;
        if (1 <= cmap[i][y] && cmap[i][y] <= 5) continue;

        cmap[i][y] = -1;
    }
}

void check() {
    memcpy(cmap, map, sizeof(map));
    for (int i = 0; i < cctv.size(); i++) {
        if (cctv[i].type == 1) {
            if (cctv[i].direction == 0) Right(cctv[i].x, cctv[i].y);
            if (cctv[i].direction == 1) Left(cctv[i].x, cctv[i].y);
            if (cctv[i].direction == 2) Down(cctv[i].x, cctv[i].y);
            if (cctv[i].direction == 3) Up(cctv[i].x, cctv[i].y);
        }
        if (cctv[i].type == 2) {
            if (cctv[i].direction == 0 || cctv[i].direction == 1) {
                Right(cctv[i].x, cctv[i].y);
                Left(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 2 || cctv[i].direction == 3) {
                Up(cctv[i].x, cctv[i].y);
                Down(cctv[i].x, cctv[i].y);
            }
        }
        if (cctv[i].type == 3) {
            if (cctv[i].direction == 0) {
                Up(cctv[i].x, cctv[i].y);
                Right(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 1) {
                Right(cctv[i].x, cctv[i].y);
                Down(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 2) {
                Down(cctv[i].x, cctv[i].y);
                Left(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 3) {
                Left(cctv[i].x, cctv[i].y);
                Up(cctv[i].x, cctv[i].y);
            }
        }
        if (cctv[i].type == 4) {
            if (cctv[i].direction == 0) {
                Left(cctv[i].x, cctv[i].y);
                Up(cctv[i].x, cctv[i].y);
                Right(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 1) {
                Up(cctv[i].x, cctv[i].y);
                Right(cctv[i].x, cctv[i].y);
                Down(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 2) {
                Right(cctv[i].x, cctv[i].y);
                Down(cctv[i].x, cctv[i].y);
                Left(cctv[i].x, cctv[i].y);
            }
            if (cctv[i].direction == 3) {
                Down(cctv[i].x, cctv[i].y);
                Left(cctv[i].x, cctv[i].y);
                Up(cctv[i].x, cctv[i].y);
            }
        }
        if (cctv[i].type == 5) {
            Right(cctv[i].x, cctv[i].y);
            Left(cctv[i].x, cctv[i].y);
            Up(cctv[i].x, cctv[i].y);
            Down(cctv[i].x, cctv[i].y);
        }
    }
}

int count_area() {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (cmap[i][j] == 0) sum++;
        }
    }
    return sum;
}

void go(int cnt) {
    if (cnt == num) {
        check();
        answer = min(answer, count_area());
        return;
    }

    cctv[cnt].direction = 0;
    go(cnt + 1);

    cctv[cnt].direction = 1;
    go(cnt + 1);

    cctv[cnt].direction = 2;
    go(cnt + 1);

    cctv[cnt].direction = 3;
    go(cnt + 1);
}

int main(void) {
    answer = 99999999;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (1 <= map[i][j] && map[i][j] <= 5) {
                cctv.push_back({i, j, map[i][j], -1});
            }
        }
    }
    num = cctv.size();
    go(0);

    cout << answer << endl;
    return 0;
}

python

import sys

sys.stdin = open('input.txt')
from copy import deepcopy


def right(x: int, y: int, copy: list) -> None:
	for j in range(y + 1, m):
		if copy[x][j] == 6:
			break
		if 1 <= copy[x][j] <= 5:
			continue
		copy[x][j] = -1


def left(x: int, y: int, copy: list) -> None:
	for j in range(y - 1, -1, -1):
		if copy[x][j] == 6:
			break
		if 1 <= copy[x][j] <= 5:
			continue
		copy[x][j] = -1


def down(x: int, y: int, copy: list) -> None:
	for i in range(x + 1, n):
		if copy[i][y] == 6:
			break
		
		if 1 <= data[i][y] <= 5:
			continue
		copy[i][y] = -1


def up(x: int, y: int, copy: list) -> None:
	for i in range(x - 1, -1, -1):
		if copy[i][y] == 6:
			break
		if 1 <= copy[i][y] <= 5:
			continue
		copy[i][y] = -1


def check() -> list:
	copy = deepcopy(data)
	for cctv in cctvs:
		x, y, type, dir = cctv
		if type == 1:
			if dir == 0:
				right(x, y, copy)
			elif dir == 1:
				left(x, y, copy)
			elif dir == 2:
				down(x, y, copy)
			elif dir == 3:
				up(x, y, copy)
		elif type == 2:
			if dir == 0 or dir == 1:
				right(x, y, copy)
				left(x, y, copy)
			elif dir == 2 or dir == 3:
				up(x, y, copy)
				down(x, y, copy)
		elif type == 3:
			if dir == 0:
				up(x, y, copy)
				right(x, y, copy)
			elif dir == 1:
				right(x, y, copy)
				down(x, y, copy)
			elif dir == 2:
				down(x, y, copy)
				left(x, y, copy)
			elif dir == 3:
				left(x, y, copy)
				up(x, y, copy)
		elif type == 4:
			if dir == 0:
				left(x, y, copy)
				up(x, y, copy)
				right(x, y, copy)
			elif dir == 1:
				up(x, y, copy)
				right(x, y, copy)
				down(x, y, copy)
			elif dir == 2:
				right(x, y, copy)
				down(x, y, copy)
				left(x, y, copy)
			elif dir == 3:
				down(x, y, copy)
				left(x, y, copy)
				up(x, y, copy)
		elif type == 5:
			right(x, y, copy)
			left(x, y, copy)
			up(x, y, copy)
			down(x, y, copy)
	
	return copy


def count_area(copy: list) -> int:
	sum = 0
	for i in range(n):
		for j in range(m):
			if copy[i][j] == 0:
				sum += 1
	return sum


def go(cnt: int) -> None:
	global answer
	if cnt == num:
		copy = check()
		answer = min(answer, count_area(copy))
		return
	
	cctvs[cnt][3] = 0
	go(cnt + 1)
	
	cctvs[cnt][3] = 1
	go(cnt + 1)
	
	cctvs[cnt][3] = 2
	go(cnt + 1)
	
	cctvs[cnt][3] = 3
	go(cnt + 1)


answer = 987654321
n, m = map(int, input().split())

data = [list(map(int, input().split())) for _ in range(n)]

cctvs = []
for i in range(n):
	for j in range(m):
		if 1 <= data[i][j] <= 5:
			cctvs.append([i, j, data[i][j], -1])
num = len(cctvs)
go(0)
print(answer)