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

1. 코드

import copy
import sys


def dfs(idx, path):
    if idx == len(cctv):
        cmd.append(path[:])
        return
    for j in d[cctv[idx][1]]:
        dfs(idx + 1, path + [j])
def up_dir(temp, x, y):
    for i in range(x - 1, -1, -1):
        if temp[i][y] == 0:
            temp[i][y] = 9
        elif 1 <= temp[i][y] <= 5 or temp[i][y] == 9:
            continue
        else:
            break
def down_dir(temp, x, y):
    global n
    for i in range(x + 1, n):
        if temp[i][y] == 0:
            temp[i][y] = 9
        elif 1 <= temp[i][y] <= 5 or temp[i][y] == 9:
            continue
        else:
            break
def left_dir(temp, x, y):
    for i in range(y - 1, -1, -1):
        if temp[x][i] == 0:
            temp[x][i] = 9
        elif 1 <= temp[x][i] <= 5 or temp[x][i] == 9:
            continue
        else:
            break
def right_dir(temp, x, y):
    global m
    for i in range(y + 1, m):
        if temp[x][i] == 0:
            temp[x][i] = 9
        elif 1 <= temp[x][i] <= 5 or temp[x][i] == 9:
            continue
        else:
            break

d = {
    1: {'u', 'd', 'l', 'r'},
    2: {'ud', 'lr'},
    3: {'ul', 'ur', 'dl', 'dr'},
    4: {'udl', 'udr', 'ulr', 'dlr'}
}
ans = 9999
n, m = map(int, sys.stdin.readline().rstrip().split())
graph = [list(map(int, sys.stdin.readline().rstrip().split()))
         for _ in range(n)]
cmd = []
cctv = []
for i in range(n):
    for j in range(m):
        # todo: cctv = ((i, j), (cctv_num))
        if 1 <= graph[i][j] <= 4:
            cctv.append(((i, j), graph[i][j]))
        elif graph[i][j] == 5:
            up_dir(graph, i, j)
            down_dir(graph, i, j)
            left_dir(graph, i, j)
            right_dir(graph, i, j)
dfs(0, [])
while cmd:
    cnt = 0
    temp_arr = copy.deepcopy(graph)
    a = cmd.pop()
    for i in range(len(cctv)):
        x, y, k = cctv[i][0][0], cctv[i][0][1], cctv[i][1]
        for j in a[i]:
            if j == 'u': up_dir(temp_arr, x, y)
            if j == 'd': down_dir(temp_arr, x, y)
            if j == 'l': left_dir(temp_arr, x, y)
            if j == 'r': right_dir(temp_arr, x, y)
    for i in temp_arr:
        cnt += i.count(0)
    ans = min(ans, cnt)
print(ans)

2. 후기

cctv는 최대 8개이다. 범위를 보고 모든 경우의 수를 조사해야 하는 문제라 생각하여 브루트 포스로 접근하였다.