[백준] 15683. 감시 - python

https://www.acmicpc.net/problem/15683

15683번: 감시

 

난이도: 골드4

알고리즘: 백트래킹

 

 

풀이과정

최대 크기가 8 x 8이고 CCTV가 최대 8개이므로 전수조사가 가능하다.

 

CCTV의 위치들을 저장하고 각 CCTV의 모든 경우에 대해 사각지대의 개수를 조사한다.

 

방문처리를 할 때 7을 더하고 방문취소를 할 때 7을 빼는 방식으로 수행하고 모든 CCTV에 대해 방문처리가 진행되면 board에서 값이 0인 칸 수를 세서 현재 가장 적은 사각지대인 answer와 비교한다.

 

소스코드

def set_visit(y, x, dy, dx, num):
    global board
    ny = y + dy
    nx = x + dx
    while 0 <= ny < N and 0 <= nx < M and board[ny][nx] != 6:
        if (ny, nx) not in cctv_pos:
            board[ny][nx] += num
        ny += dy
        nx += dx


def backtracking(idx):
    if idx == len(cctv_pos):
        global answer
        count = 0
        for i in range(N):
            for j in range(M):
                if board[i][j] == 0:
                    count += 1
        answer = min(answer, count)
        return

    y, x = cctv_pos[idx]
    if board[y][x] == 1:
        for i in range(4):
            # 방문 처리
            set_visit(y, x, dy[i], dx[i], 7)
            backtracking(idx + 1)
            # 방문 취소
            set_visit(y, x, dy[i], dx[i], -7)
    elif board[y][x] == 2:
        for i in range(2):
            set_visit(y, x, dy[i], dx[i], 7)
            set_visit(y, x, dy[i + 2], dx[i + 2], 7)
            backtracking(idx + 1)
            set_visit(y, x, dy[i], dx[i], -7)
            set_visit(y, x, dy[i + 2], dx[i + 2], -7)
    elif board[y][x] == 3:
        for i in range(4):
            set_visit(y, x, dy[i], dx[i], 7)
            set_visit(y, x, dy[(i + 1) % 4], dx[(i + 1) % 4], 7)
            backtracking(idx + 1)
            set_visit(y, x, dy[i], dx[i], -7)
            set_visit(y, x, dy[(i + 1) % 4], dx[(i + 1) % 4], -7)
    elif board[y][x] == 4:
        for i in range(4):
            set_visit(y, x, dy[i], dx[i], 7)
            set_visit(y, x, dy[(i + 1) % 4], dx[(i + 1) % 4], 7)
            set_visit(y, x, dy[(i + 2) % 4], dx[(i + 2) % 4], 7)
            backtracking(idx + 1)
            set_visit(y, x, dy[i], dx[i], -7)
            set_visit(y, x, dy[(i + 1) % 4], dx[(i + 1) % 4], -7)
            set_visit(y, x, dy[(i + 2) % 4], dx[(i + 2) % 4], -7)
    elif board[y][x] == 5:
        for i in range(4):
            set_visit(y, x, dy[i], dx[i], 7)
        backtracking(idx + 1)
        for i in range(4):
            set_visit(y, x, dy[i], dx[i], -7)


N, M = map(int, input().split())
board = [[0 for _ in range(M)] for _ in range(N)]
cctv_pos = []
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
answer = 100
for i in range(N):
    row = list(map(int, input().split()))
    for j in range(M):
        if row[j] != 0 and row[j] != 6:
            cctv_pos.append((i, j))
        board[i][j] = row[j]
backtracking(0)
print(answer)