문제
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()