🦊 감시

1. 문제 링크

15683번: 감시

2. 코드

Python3 31708KB 2852ms

stack = []
MAP = []
    
MIN = 10000
blocked = 0
def backtracking(depth):
    global MAP
    global MIN
    global N, M, D
    global stack
    global camera
    global blocked
    if depth == D:
        MIN = min(MIN, N * M - blocked - len(stack))
        return
        
    x, y = camera[depth]
    delta = [[0, 1], [1, 0], [0, -1], [-1, 0], ] #상우하좌
    if MAP[y][x] == 1:
        for dx, dy in delta:
            count = doWatch(x, y, [dx, dy])
            # 한쪽을 투영했으니 다음 백트래킹
            backtracking(depth + 1)
            # 원상 복구
            for _ in range(count):
                stack.pop()
    elif MAP[y][x] == 2:
        for i in range(2):
            dx, dy = delta[i]
            count = doWatch(x, y, [dx, dy])
            dx, dy = delta[i + 2]
            count += doWatch(x, y, [dx, dy])
            # 한쪽을 투영했으니 다음 백트래킹
            backtracking(depth + 1)
            # 원상 복구
            for _ in range(count):
                stack.pop()
    elif MAP[y][x] == 3:
        for i in range(4):
            dx, dy = delta[i]
            count = doWatch(x, y, [dx, dy])
            dx, dy = delta[(i + 1) % 4]
            count += doWatch(x, y, [dx, dy])
            # 한쪽을 투영했으니 다음 백트래킹
            backtracking(depth + 1)
            # 원상 복구
            for _ in range(count):
                stack.pop()
    elif MAP[y][x] == 4:
        for i in range(4):
            dx, dy = delta[i]
            count = doWatch(x, y, [dx, dy])
            dx, dy = delta[(i + 1) % 4]
            count += doWatch(x, y, [dx, dy])
            dx, dy = delta[(i + 2) % 4]
            count += doWatch(x, y, [dx, dy])
            # 한쪽을 투영했으니 다음 백트래킹
            backtracking(depth + 1)
            # 원상 복구
            for _ in range(count):
                stack.pop()
    elif MAP[y][x] == 5:
        dx, dy = delta[0]
        count = doWatch(x, y, [dx, dy])
        dx, dy = delta[1]
        count += doWatch(x, y, [dx, dy])
        dx, dy = delta[2]
        count += doWatch(x, y, [dx, dy])
        dx, dy = delta[3]
        count += doWatch(x, y, [dx, dy])
        # 한쪽을 투영했으니 다음 백트래킹
        backtracking(depth + 1)
        # 원상 복구
        for _ in range(count):
            stack.pop()

def doWatch(x, y, delta):
    global MAP
    global stack
    global N, M
    global camera
    dx, dy = delta
    nx = x
    ny = y
    count = 0
    while True:
        nx = nx + dx
        ny = ny + dy
        if 0 <= nx < M and 0 <= ny < N:
            # 벽을 마주함
            if MAP[ny][nx] == 6:
                break
            # 이미 검사한 곳 통과
            if [nx, ny] in stack or [nx, ny] in camera:
                continue
            # 검사한 곳 저장
            stack.append([nx, ny])
            count += 1
        else:
            break
    return count
            
camera = []
N, M = map(int, input().split())
for i in range(N):
    MAP.append(list(map(int, input().split())))
    for j in range(M):
        if 1 <= MAP[i][j] <= 5:
            camera.append([j, i])
            blocked += 1
        if MAP[i][j] == 6:
            blocked += 1
D = len(camera)

backtracking(0)
print(MIN)

3. 해설

python3 31120kb 520ms

약간의 노가다성 백트래킹 문제

1번부터 5번 유형의 카메라 위치를 기억하고 while 문을 돌려서 벽에 닿을때 까지 스택에 감시할 위치를 저장

이때 카메라와 이미 검사한 지점은 방문 체크 (stack) 를 통해 기억하고 저장하지 않음

카메라의 개수와 depth 가 일치하면 백트래킹 종료

이후 재귀를 빠져나올 때 감시 시작한 지점의 개수 만큼 stack 에서 pop 해주어 원복 시킴