15683번 – 감시

1

문제

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

풀이

코드

from copy import deepcopy
from math import inf

r, c = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(r)]
EMPTY, WALL, LIGHT, _min = (0, 6, '#', inf)
board = [[WALL]*c] + board + [[WALL]*c]
for y in range(len(board)):
  board[y] = [WALL] + board[y] + [WALL]
CCTVS = []
for y in range(len(board)):
  for x in range(len(board[y])):
    if 1 <= board[y][x] <= 5:
      CCTVS.append((y, x, board[y][x]))
n = len(CCTVS)
동, 서, 남, 북 = (0, 1, 2, 3)
ways = []
dyx = [(0, 1), (1, 0), (0, -1), (-1, 0)]
_min = inf

def 구십도(d):
  d = d-1
  if d == -1: d = 3
  return d

def 반대방향(d):
  if d < 2: return d+2
  else: return d-2

def 한줄쫙(y, x, d, B):
  dy, dx = dyx[d]
  while(True):
    y, x = (y+dy, x+dx)
    if B[y][x] == WALL: break
    if B[y][x] == EMPTY: B[y][x] = LIGHT
    

def 감시감시데스():
  B = deepcopy(board)
  for i in range(len(CCTVS)):
    y, x, CCTV = CCTVS[i]
    d = ways[i]
    한줄쫙(y, x, d, B) # 기본데스
    if CCTV == 2: 한줄쫙(y, x, 반대방향(d), B)
    elif CCTV == 3: 한줄쫙(y, x, 구십도(d), B)
    elif CCTV == 4:
      한줄쫙(y, x, 반대방향(d), B)
      한줄쫙(y, x, 구십도(d), B)
    elif CCTV == 5:
      한줄쫙(y, x, 반대방향(d), B)
      한줄쫙(y, x, 구십도(d), B)
      d = 구십도(d)
      한줄쫙(y, x, 반대방향(d), B)  
  return 감시된곳찾기(B)
  
def 감시된곳찾기(B):
  count = 0
  for y in range(len(B)):
    for x in range(len(B[y])):
      if B[y][x] == EMPTY: count += 1
  return count

def DFS(depth):
  global _min
  if depth == n:
    _min = min(_min, 감시감시데스())
    return
  for i in range(4): # 북 동 남 서
    ways.append(i)
    DFS(depth+1)
    ways.pop()

def answer():
  DFS(0)
  print(_min)
  
answer()

Add Comment