15683_감시

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

15683번: 감시

 

 

 

먼저 cctv가 5개가 있는데 해당 cctv들의 각 방향마다 체크할 방향들을 세트로 묶어두었다.

 

예를 2번 cctv라면

[ [[0,1],[0,-1]] , [[1,0],[-1,0]] ]

위와같이 총 2개의 방향을 가지고 각각 상하나 좌우를 보게 된다.

 

이렇게 cctv 번호마다 방향을 정해주고 cctv가 몇개있는지 세주고, dfs를 사용해서 모든 경우를 체크했다.

 

위에서부터 내려가면서 각 방향을 dfs로 체크해준 후, 만약 마지막 cctv라면 사각지대의 개수를 세서 만약 사각지대 개수가 더 작다면 갱신해준다.

 

또한 마지막에 예외처리로 cctv가 한개도 없는경우만 생각해주었다.

 

import sys
input = sys.stdin.readline

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

cctv_info = [0]*6
cctv_info[1] = [ [[0,1]], [[1,0]] , [[0,-1]] , [[-1,0]] ]
cctv_info[2] = [ [[0,1],[0,-1]] , [[1,0],[-1,0]] ]
cctv_info[3] = [ [[-1,0],[0,1]],[[0,1],[1,0]],[[1,0],[0,-1]] ,[[0,-1],[-1,0]]]
cctv_info[4] = [ [[0,-1],[-1,0],[0,1]] ,[[-1,0],[0,1],[1,0]],[[0,1],[1,0],[0,-1]],[[1,0],[0,-1],[-1,0]] ]
cctv_info[5] = [ [[0,1],[1,0],[0,-1],[-1,0]] ]

cctvs = []
for i in range(n):
    for j in range(m):
        if board[i][j] != 0 and board[i][j] != 6:
            cctvs.append([board[i][j],i,j])
len_cctv = len(cctvs)

def check_size():
    cnt = 0
    for i in board:
        for j in i:
            if j == 0:
                cnt +=1
    return cnt

result = 10e9

def dfs(cctv,odr):
    global board,result
    num,x,y = cctv

    for direct in cctv_info[num]:
        old_board = [x[:] for x in board]
        for dx,dy in direct:
            nx,ny = x + dx,y + dy


            while 0<= nx < n and 0<= ny < m and board[nx][ny] != 6:
                if not board[nx][ny]:
                    board[nx][ny] = '#'

                nx,ny = nx + dx,ny + dy

        nx_odr = odr + 1
        if nx_odr == len_cctv:
            result = min(result,check_size())
        elif nx_odr < len_cctv:
            dfs(cctvs[nx_odr],nx_odr)

        board = [x[:] for x in old_board]

if len_cctv==0:
    print(check_size())
else:
    dfs(cctvs[0],0)
    print(result)