백준 15683 감시 (파이썬)

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

15683번: 감시

1. 사무실 크기를 입력받고 넓이를 area 변수에 저장한다

2. cctv 1~4는 cctv 리스트에 저장하고 cctv 5는 cctv5 리스트에 저장한다

   cctv와 벽을 만나면 area에 1을 빼서 구역의 넓이를 갱신한다

3. cctv5는 4방향을 감시할 수 있으므로 먼저 처리한다

   감시 가능한 구역을 -1로 표시하고 area에 1을 뺀다

4. 이제 dfs로 각 cctv의 모든 방향에 대해서 검사한다

   cctv 2는 다른 cctv와 다르게 2방향에 대한 경우밖에 없지만 따로 처리하지는 않았다

5. 각 cctv가 감시할 방향을 정했으면 move함수로 감시 가능한 구역의 개수를 return 받아 c에 저장한다

6. area - c를 하면 사각 지대의 크기를 구할 수 있으므로 최소값을 구하여 출력한다

from collections import deque
from copy import deepcopy
import sys

input = sys.stdin.readline
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def dfs(cnt):
    global ans, temp_a
    if cnt == len(cctv):
        temp_a = deepcopy(a)
        c = 0
        for i in range(len(cctv)):
            x, y = cctv[i]
            if a[x][y] == 1:
                c += move(x, y, dir[i])
            elif a[x][y] == 2:
                c += move(x, y, dir[i])
                c += move(x, y, (dir[i] + 2) % 4)
            elif a[x][y] == 3:
                c += move(x, y, dir[i])
                c += move(x, y, (dir[i] + 1) % 4)
            else:
                c += move(x, y, dir[i])
                c += move(x, y, (dir[i] + 1) % 4)
                c += move(x, y, (dir[i] + 2) % 4)
        ans = min(ans, area - c)
        return

    for i in range(4):
        dir.append(i)
        dfs(cnt + 1)
        dir.pop()


def move(x, y, d):
    cnt = 0
    while True:
        nx = x + dx[d]
        ny = y + dy[d]
        if not 0 <= nx < n or not 0 <= ny < m or temp_a[nx][ny] == 6:
            return cnt
        if 0 < temp_a[nx][ny] < 6 or temp_a[nx][ny] == -1:
            x, y = nx, ny
            continue
        temp_a[nx][ny] = -1
        cnt += 1
        x, y = nx, ny


n, m = map(int, input().split())
area = n * m
a, cctv, cctv5 = [], [], []
for i in range(n):
    row = list(map(int, input().split()))
    a.append(row)
    for j in range(m):
        if 0 < a[i][j] < 5:
            cctv.append([i, j])
            area -= 1
        elif a[i][j] == 5:
            cctv5.append([i, j])
            area -= 1
        elif a[i][j] == 6:
            area -= 1

for i in range(len(cctv5)):
    x, y = cctv5[i]
    for i in range(4):
        nx, ny = x, y
        while True:
            nx += dx[i]
            ny += dy[i]
            if not 0 <= nx < n or not 0 <= ny < m or a[nx][ny] == 6:
                break
            if 0 < a[nx][ny] < 6 or a[nx][ny] == -1:
                continue
            a[nx][ny] = -1
            area -= 1

dir = deque()
ans = area
dfs(0)
print(ans)