[Baekjoon-Python] 15683 : 감시

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

접근

각각의 cctv마다 감시할 수 있는 경우의 수

cctv 경우의 수

1번 4

2번 2

3번 4

4번 4

5번 1
cctv를 dfs 탐색해서 감시할 수 있는 모든 경우의 수를 구한다.
탐색이 끝나면 사각 지대의 크기를 구한다.

cctv	경우의 수
1번	4
2번	2
3번	4
4번	4
5번	1

풀이

from sys import stdin


def dfs(office, idx):
    global res

    if idx >= len(cctv):
        blind_spot = sum(o.count(0) for o in office)
        res = min(res, blind_spot) # (1)
        return

    r, c = cctv[idx]
    if office[r][c] == 1: # (2)
        for i in range(4):
            tmp_office = [o[:] for o in office]
            watch(tmp_office, r, c, direction[i][0], direction[i][1])
            dfs(tmp_office, idx + 1)
    elif office[r][c] == 2: # (3)
        for i in range(2):
            tmp_office = [o[:] for o in office]
            watch(tmp_office, r, c, direction[i][0], direction[i][1])
            watch(tmp_office, r, c, -direction[i][0], -direction[i][1])
            dfs(tmp_office, idx + 1)
    elif office[r][c] == 3: # (4)
        for i in range(4):
            tmp_office = [o[:] for o in office]
            watch(tmp_office, r, c, direction[i][0], direction[i][1])
            watch(tmp_office, r, c, direction[(i + 1) % 4][0], direction[(i + 1) % 4][1])
            dfs(tmp_office, idx + 1)
    elif office[r][c] == 4: # (5)
        for i in range(4):
            tmp_office = [o[:] for o in office]
            watch(tmp_office, r, c, direction[i][0], direction[i][1])
            watch(tmp_office, r, c, direction[(i + 1) % 4][0], direction[(i + 1) % 4][1])
            watch(tmp_office, r, c, direction[(i + 2) % 4][0], direction[(i + 2) % 4][1])
            dfs(tmp_office, idx + 1)
    else: # (6)
        for i in range(4):
            watch(office, r, c, direction[i][0], direction[i][1])
        dfs(office, idx + 1)


def watch(office, r, c, dr, dc): # (7)
    while True:
        r += dr
        c += dc
        if r < 0 or r >= n or c < 0 or c >= m or office[r][c] == 6:
            break

        if office[r][c] == 0:
            office[r][c] = '#'


n, m = map(int, stdin.readline().split())
office = []
cctv = []
for i in range(n):
    o = list(map(int, stdin.readline().split()))
    for j in range(m):
        if 0 < o[j] < 6:
            cctv.append((i, j))
    office.append(o)

res = 1e9
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
dfs(office, 0)

print(res)