풀이
CCTV 의 개수에 따라서 감시 범위의 경우의 수가 주어진다. 이를 해결하기 위해 DFS 를 통해 재귀적으로 풀 수 있다.
먼저 CCTV 의 종류에 따라 감시 방향을 정의해준다. 한번에 감시할 수 있는 방향이 여러가지인 경우도 있기 때문에 각 CCTV 의 감시 방향 경우에 따라서 감시 방향을 리스트에 저장해준 뒤 경우의 수에 따라 다시 한 번 리스트로 감싸준다.
이후 입력을 받으면서 CCTV 의 종류와 좌표를 cctvs 에 저장해준 뒤 dfs 를 실행한다.
각 CCTV 의 방향과 좌표에 따라서 2 차원 배열을 수정해 줄 watch 함수를 선언한다.
이후 각 CCTV 의 종류와 2 차원 배열을 받고 CCTV 의 종류를 cam_num 변수에 저장한 뒤 cam_num 을 인덱스로 활용해 direction 에서 감시 방향의 경우의 수를 반복문을 통해 watch 함수와 dfs 를 재귀적으로 실행시킨다.
예를 들어 2 차원 배열에 2번 CCTV 와 4번 CCTV 가 있을 경우,
2번 CCTV 는 [[0, 1], [2, 3]] 로 총 2 가지 경우의 수가 있고
4번 CCTV 는 [[3, 0, 2], [1, 3, 0], [0, 2, 1], [2, 1, 3]] 로 총 4 가지 경우의 수가 있다.
이럴 경우 cctvs 에는 [[2, x, y], [4, x, y]] 가 저장될 것이다.
dfs 를 실행시키면 첫 번째 CCTV 인 2번 CCTV 에 대한 dfs 가 실행되고,
for d in direction[can_num] = for d in direction[2] = for d in [[0, 1], [2, 3]] 가 된다.
이후 d = [0, 1] 에 대한 watch 함수와 dfs 가 실행되는데 watch 에선,
for d in direction = for d in [0, 1] 이 되고 각 d 에 따라서 감시 범위를 수정한 뒤 dfs 를 실행한다.
정리하자면,
for d in [[0, 1], [2, 3]]:
watch(d)
for d in [[3, 0, 2], [1, 3, 0], [0, 2, 1], [2, 1, 3]]:
watch(d)
에 대한 2중 반복문이 실행되는 것이다.
첫 DFS 문제여서 역시 많은 코드를 참고했고 추후에 풀어볼 문제에 많은 도움이 될 것 같다.
소스코드
# 감시
import sys
import copy
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
direction = [[], [[0], [1], [2], [3]], [[0, 1], [2, 3]], [[0, 2], [2, 1], [1, 3], [3, 0]], [[3, 0, 2], [1, 3, 0], [0, 2, 1], [0, 2, 1], [2, 1, 3]], [[0, 1, 2, 3]]] # CCTV 종류에 따른 감시 범위를 리스트로 선언
def watch(x, y, direction, temp):
for d in direction: # 배치에 따른 감시 방향 ex) 2번의 1번째 감시 경우의 수 [0, 1]
nx = x
ny = y
while True:
nx += dx[d]
ny += dy[d]
if 0 <= nx < n and 0 <= ny < m and temp[nx][ny] != 6:
if temp[nx][ny] == 0:
temp[nx][ny] = "#"
else:
break
def dfs(office, cctv):
global ans
temp = copy.deepcopy(office) # 경우의 수에 따라 감시 범위가 달라지기 때문에 복제를 사용
if cctv == len(cctvs): # 총 CCTV 개수 만큼의 재귀에 들어왔을 경우
c = 0
for i in temp:
c += i.count(0)
ans = min(ans, c)
return
cam_num, x, y = cctvs[cctv]
for d in direction[cam_num]: # CCTV 종류에 따른 감시 방향 ex) 2번 일 경우 [[0, 1], [2, 3]]
watch(x, y, d, temp) # [0, 1] 에 대한 감시범위 and [2, 3] 에 대한 감시범위
dfs(temp, cctv+1) # 다음 CCTV에 대한 DFS
temp = copy.deepcopy(office)
n, m = map(int, input().split())
office = []
cctvs = [] # 사무실에 있는 CCTV 별 [종류, x, y]
ans = n * m
for i in range(n):
line = list(map(int, input().split()))
office.append(line)
for j in range(m):
if 0 < line[j] < 6:
cctvs.append((line[j], i, j))
dfs(office, 0) # CCTV 개수에 따라 경우의 수가 달라지기 때문에 DFS 사용
print(ans)