[코딩인터뷰] 백준 15683번 감시

백준 15683번 감시

import sys
from copy import deepcopy
rl = sys.stdin.readline

def watch(testbed, sr, sc, direction):
    direction %= 4

    cr = sr + DR[direction]
    cc = sc + DC[direction]
    while 0 <= cr < N and 0 <= cc < M:

        if testbed[cr][cc] == 6:
            break

        if testbed[cr][cc] == 0:
            testbed[cr][cc] = -1

        cr += DR[direction]
        cc += DC[direction]

def spread(cctv_directions):
    global ANSWER

    testbed = deepcopy(BOARD)
    for cctv_id in range(len(CCTV)):
        if CCTV[cctv_id][2] == 1:
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id])
        elif CCTV[cctv_id][2] == 2:
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id])
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 2)
        elif CCTV[cctv_id][2] == 3:
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id])
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 1)
        elif CCTV[cctv_id][2] == 4:
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id])
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 1)
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 2)
        elif CCTV[cctv_id][2] == 5:
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id])
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 1)
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 2)
            watch(testbed, CCTV[cctv_id][0], CCTV[cctv_id][1], cctv_directions[cctv_id] + 3)

    count = 0
    for i in range(N):
        for j in range(M):
            if testbed[i][j] == 0:
                count += 1

    if count < ANSWER:
        ANSWER = count

def dfs(cctv_directions):
    if len(CCTV) == len(cctv_directions):
        spread(cctv_directions)
        return

    next_cctv_id = len(cctv_directions)
    if CCTV[next_cctv_id][2] == 1:
        for direction in range(4):
            cctv_directions.append(direction)
            dfs(cctv_directions)
            cctv_directions.pop()
    elif CCTV[next_cctv_id][2] == 2:
        for direction in range(2):
            cctv_directions.append(direction)
            dfs(cctv_directions)
            cctv_directions.pop()
    elif CCTV[next_cctv_id][2] == 3:
        for direction in range(4):
            cctv_directions.append(direction)
            dfs(cctv_directions)
            cctv_directions.pop()
    elif CCTV[next_cctv_id][2] == 4:
        for direction in range(4):
            cctv_directions.append(direction)
            dfs(cctv_directions)
            cctv_directions.pop()
    elif CCTV[next_cctv_id][2] == 5:
        cctv_directions.append(0)
        dfs(cctv_directions)
        cctv_directions.pop()

N, M = map(int, rl().split())
BOARD = []
CCTV = []
for a in range(N):
    BOARD.append(list(map(int, rl().split())))
    for b in range(M):
        if 1 <= BOARD[a][b] <= 5:
            CCTV.append((a, b, BOARD[a][b]))

ANSWER = int(1e9)
# R D L U
DR = [1, 0, -1, 0]
DC = [0, 1, 0, -1]
dfs([])

print(ANSWER)