[백준/Python] 15683번 감시

www.acmicpc.net/problem/15683

15683번: 감시

---

---

Solution

import copy
INF = int(1e9)

# 동 서 남 북
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], [2, 1, 3]], [[0, 1, 2, 3]]]

def watch(y, x, direction, tmp):
    for d in direction:
        nx = x
        ny = y
        while True:
            nx += dx[d]
            ny += dy[d]
            if nx >= 0 and nx < m and ny >= 0 and ny < n and tmp[ny][nx] != 6:
                if tmp[ny][nx] == 0:
                    tmp[ny][nx] = '#'
            else:
                break

def dfs(office, cnt):
    global ans

    tmp = copy.deepcopy(office)
    if cnt == cctv_cnt:
        c = 0
        for i in tmp:
            c += i.count(0)
        ans = min(ans, c)
        return
    y, x, cctv = q[cnt]
    for i in direction[cctv]:
        watch(y, x, i, tmp)
        dfs(tmp, cnt + 1)
        tmp = copy.deepcopy(office)

n, m = map(int, input().split())
office = []
cctv_cnt = 0
q = []
ans = INF
for i in range(n):
    input_data = list(map(int, input().split()))
    office.append(input_data)
    for j in range(len(input_data)):
        if input_data[j] != 0 and input_data[j] != 6:
            cctv_cnt += 1
            q.append([i, j, input_data[j]])

dfs(office, 0)
print(ans)

 

각 CCTV가 감시하는 방향을 회전하는 것을 포함해서 direction이라는 변수에 담아둔다.

 

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], [2, 1, 3]], [[0, 1, 2, 3]]]

 

CCTV번호가 인덱스가 되게끔 값을 설정해준다.

1번 CCTV는 상하좌우 네 방향을 볼 수 있기 때문에 0, 1, 2, 3을 넣어주고 2번 CCTV는 동서 방향과 남북 방향으로 [0, 1]과 [2, 3]을 넣어주는 식이다.

 

입력을 받을 때는 CCTV의 개수를 구해놓고, 해당 CCTV의 좌표와 번호를 큐에 담아준다.

그리고 dfs를 실행한다. dfs에서는 CCTV의 개수 만큼 함수를 재귀적으로 돈다. 만약 cnt가 CCTV의 개수와 같아질 경우 사각지대를 구하고 정답을 갱신한다.

cnt는 큐에 있는 CCTV에 접근하는 인덱스 역할도 한다. 현재 CCTV를 꺼내서 x, y, cctv변수에 담고 해당 CCTV번호가 감시할 수 있는 방향이 담긴 direction[cctv]를 하나씩 검사한다.