알고리즘/백준
[백준 파이썬] 15683 감시
rocku
2023. 7. 27. 11:36
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
0, 0, 0
0, 3, 0
0, 0, 0
과 같은 입력을 줘서 모든 CCTV가 정확한 방향을 가르키는지, 회전이 잘 되는지 출력해 봐야 한다.
from copy import deepcopy
N, M = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(N)]
cctv = []
for n in range(N):
for m in range(M):
if office[n][m] not in [0, 6]:
cctv.append([n, m, office[n][m]])
rotate_90 = [[0, 1],
[-1, 0]]
def cctv_n(office, num, n, m, d):
# 1번 cctv를 사용해서 다른 cctv를 만들어준다.
def cctv_1(office, n, m, d):
while (0 <= n < N
and 0 <= m < M): # 사무실 내에서
nn, nm = n + d[0], m + d[1] # 벽이 아닐때까지 이동하며
if (0 <= nn < N and 0 <= nm < M): # 감시 가능 구간으로 설정
if office[nn][nm] == 0:
office[nn][nm] = "#"
elif office[nn][nm] == 6:
break
n, m = nn, nm
return office
if num == 1: # 1번 cctv는 한 방향만 감시
return cctv_1(office, n, m, d)
elif num == 2: # 2번 cctv는 한 직선으로 감시하므로
office = cctv_1(office, n, m, d)
for _ in range(2): # 90도 회전을 두 번 적용 후 감시 범위 확인
d = [d[0]*rotate_90[0][0] + d[1]*rotate_90[0][1],
d[0]*rotate_90[1][0] + d[1]*rotate_90[1][1]]
return cctv_1(office, n, m, d)
else:
for i in range(num-2): # 나머지는 90도 단위로 회전하므로
office = cctv_1(office, n, m, d) # 감시 범위에 따라 회전 후 적용
d = [d[0]*rotate_90[0][0] + d[1]*rotate_90[0][1],
d[0]*rotate_90[1][0] + d[1]*rotate_90[1][1]]
return cctv_1(office, n, m, d)
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]] # E, S, W, N
min_count = 64
arr = []
def back_tracking(depth):
global min_count
if depth == len(cctv):
count = 0
office_copy = deepcopy(office)
# 각 cctv마다 시작 방향 지정
for (n, m, num), d in zip(cctv, arr):
office_copy = cctv_n(office_copy, num, n, m, direction[d])
for row in office_copy:
count += row.count(0)
min_count = min(min_count, count)
return
else:
for i in range(4):
arr.append(i)
back_tracking(depth+1)
arr.pop()
back_tracking(0)
print(min_count)