문제 링크

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

문제 설명

• 감시하는 범위가 각각 다른 5종류의 cctv가 있다
• 감시받지 않는 영역의 최솟값 출력

풀이

• 완전 탐색
• 재귀로 각 cctv가 바라보는 방향의 4가지 경우의 수 모두 구함
  • 4 ** len(cctv)
  • 2번, 5번은 4가지 방향을 모두 검사하지 않아도 되지만 시간복잡도는 차이 없을 것 같아서 구현의 편의상 그냥 검사했다
• 각 경우의 수마다 감시받지 않는 영역의 넓이를 구함
• 최솟값 출력

코드

def dfs(i):
    global min_size
    if i == len(cctv):
        min_size = min(min_size, get_size())
        return
    for d in range(4):
        dirs[i] = d
        dfs(i+1)


def get_size():
    new_board = [line[:] for line in board]
    for i in range(len(cctv)):
        set_board(new_board, i)
    return sum([line.count(0) for line in new_board])


def set_board(board, i):
    y, x, num = cctv[i]
    d = dirs[i]
    if num == 1:
        set_line(board, y, x, d)
    elif num == 2:
        set_line(board, y, x, d)
        set_line(board, y, x, (d+2)%4)
    elif num == 3:
        set_line(board, y, x, d)
        set_line(board, y, x, (d+1)%4)
    elif num == 4:
        set_line(board, y, x, d)
        set_line(board, y, x, (d+1)%4)
        set_line(board, y, x, (d+2)%4)
    elif num == 5:
        for j in range(4):
            set_line(board, y, x, j)


def set_line(board, y, x, d):
    while True:
        y, x = y + dy[d], x + dx[d]
        if 0 <= y < h and 0 <= x < w:
            if board[y][x] == 0:
                board[y][x] = 7
            elif board[y][x] == 6:
                break
        else:
            break

# init
import sys
read = sys.stdin.readline
h, w = map(int, read().split())
board = [list(map(int, read().split())) for _ in range(h)]
cctv = []
for i in range(h):
    for j in range(w):
        if 1 <= board[i][j] <= 5:
            cctv.append([i, j, board[i][j]])
visited = [False] * len(cctv)
dirs = [-1] * len(cctv)
min_size = float('inf')
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]   # 북,동,남,서

# start
dfs(0)
print(min_size)