BOJ 15683 - 감시

풀이

---

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)

References

---

• BOJ 15683 - 감시