15683 : 감시 - Python

풀이

아래에서 다루는 CCTV 설치 예시는 (0, 0)을 기준으로 했다.

 

1번 CCTV

초기 → (0, 1) 만 감시가능

이후 최대 3번 회전 가능 → (1, 0), (0, -1), (-1, 0) 감시 가능

 

2번 CCTV

초기 → (0, -1), (0, 1) 감시 가능

최대 1번 회전 가능 → (-1, 0), (1, 0)

3번 CCTV

초기 → (-1, 0), (0, 1) 감시 가능

최대 3번 회전 가능 → [(1, 0), (0, 1)], [(1, 0), (0, -1)], [(-1, 0), (0, -1)]

4번 CCTV

초기 → (-1, 0), (0, -1), (0, 1) 감시 가능

최대 3번 회전 가능 → [(-1, 0), (0, 1), (1, 0)], [(0, -1), (0, 1), (1, 0)], [(-1, 0), (1, 0), (0, -1)]

5번 CCTV

초기 → (-1, 0), (0, 1), (1, 0), (0, -1) 감시 가능

회전 X

위와 같이 CCTV에서 나올 수 있는 모든 경우의 수를 직접 계산하고 이를 저장했다.

그리고 CCTV 감시하는 부분의 경우 벽을 발견한 부분의 경우에만 멈추도록 했다. 이는 CCTV 방향이 겹치는 경우가 있을 수 있기 때문이다.

 

 

백트래킹 함수는 두 부분으로 나눌 수 있다. 첫 부분은 모든 CCTV 조작을 한 뒤 사각지대를 세는 부분이다.

if idx == len(cctv):
    cnt = 0
    for i in range(len(v)):
        cnt += v.count(False)
    ans = min(ans, cnt)
    return

이를 위해서 감시 카메라의 유형과 좌표를 따로 리스트로 저장하고 인덱스로 관리해야 한다.

 

두 번째 부분은 실제 CCTV를 조작하는 부분이다. 현재 idx를 기준으로 CCTV를 할당했고  cctv_num을 통해 위에서 계산한 CCTV 유형에 맞는 감시 방향을 할당해줬다. 이후에는 재귀를 통해 다음 CCTV를 조작하도록 했다.

# 방문 처리 로직
for dir in CCTV_DIR[cctv_num]:
    new_v = [[v[i][j] for j in range(M)] for i in range(N)]
    for move in dir:
        dy, dx = move
        for i in range(1, 8):  # 최대 8
            ny, nx = y + dy * i, x + dx * i
            if ny >= N or nx >= M or ny < 0 or nx < 0 or _map[ny][nx] == WALL:
                break
            new_v[ny][nx] = True

시간초과.. GG

백준 15683 - 감시 (python)
BOJ - 감시 15683번 (python)

로직은 맞는 것 같은데 시간 초과를 해결하지 못하겠어서 결국 다른 분들 풀이를 참고했다. 코드가 전반적으로 비슷한데 안되는 부분이 어딜까하고 찾아봤는데 어처구니 없는 실수를 했다.

for i in range(idx, len(cctv)):  # 이 부분이 문제...
    y, x = cctv[i]
    cctv_num = _map[y][x] - 1
    for dir in CCTV_DIR[cctv_num]:
        new_v = deepcopy(v)
        for dy, dx in dir:
            for i in range(1, N + 1):  # 최대 8
                ny, nx = y + dy * i, x + dx * i
                if ny >= N or nx >= M or ny < 0 or nx < 0 or _map[ny][nx] == WALL:
                    break
                new_v[ny][nx] = True

DFS 내부에서 불필요한 반복을 도는 구간이 있었다. 재귀에서 현재 인덱스의 CCTV만 조작을 해야하는데, 다음 재귀에서 조작할 CCTV까지 한 번에 조작해버렸다.. 그래서 한 재귀 안에서 (N - i)!을 추가로 더 수행했고 이게 시간 초과를 냈다.

그리고 참고 글 중 deepcopy를 사용하면 시간 차이가 많이 난다는 이야기가 있어 직접 확인해봤다.

위에 있는 제출이 deepcopy를 사용한 것이고 아래가 list comprehension을 사용한 풀이였는데 3 ~ 4배 차이가 난다.. 눈으로 보니 차이가 크다.

전체 코드

import sys

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
# f = open("input.txt", "rt")
# input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출
WALL = 6
DIRECTIONS = (-1, 0), (0, 1), (1, 0), (0, -1)
CCTV_DIR = [
    [[1], [2], [3], [0]],  # 1번
    [[0, 2], [1, 3]],  # 2번
    [[0, 1], [1, 2], [2, 3], [3, 0]],  # 3번
    [
        [0, 1, 3],
        [0, 1, 2],
        [1, 2, 3],
        [0, 2, 3],
    ],  # 4번
    [[1, 2, 3, 0]],  # 5번
]

N, M = map(int, input().split())
v = [[False] * M for _ in range(N)]
ans = N * M + 1
_map = []
cctv = []
for i in range(N):
    row = list(map(int, input().split()))
    for j in range(M):
        if row[j] == WALL:
            v[i][j] = True
            continue
        if row[j] < 1:
            continue
        cctv.append((row[j] - 1, i, j))
        v[i][j] = True
    _map.append(row)

def find(idx: int, v: list):
    global ans
    if idx == len(cctv):  # 마지막 원소 체크 시
        cnt = 0
        for i in range(N):
            cnt += v[i].count(False)
        ans = min(ans, cnt)
        return

    cctv_num, y, x = cctv[idx]
    for dir in CCTV_DIR[cctv_num]:
        new_v = [[v[i][j] for j in range(M)] for i in range(N)]

        for move in dir:
            dy, dx = DIRECTIONS[move]
            for i in range(1, 8):  # 최대 8
                ny, nx = y + dy * i, x + dx * i
                if ny >= N or nx >= M or ny < 0 or nx < 0 or _map[ny][nx] == WALL:
                    break
                new_v[ny][nx] = True

        find(idx + 1, new_v)

def main():
    find(0, v)
    print(ans)

if __name__ == "__main__":
    main()