15683번 - 감시

문제

 

15683번: 감시 (acmicpc.net)

15683번: 감시

풀이 1

각 감시카메라를 네 방향으로 돌려보며 전체 보드에서 빈 칸의 개수가 최소가 되게하는 경우를 찾는 전형적인 백트래킹, DFS 문제이다. 큰 구조는 미리 구해놓은 감시카메라 좌표를 백트래킹 하며, 네  방향씩 돌려보는 것이다. 카메라의 방향이 90도 돌아가는 것은 0,1,2,3을 각각 북,동,남,서라고 했을 때 1씩 더해주기만 하면 된다. 이때 감시카메라가 감시하는 영역은 서로 겹칠 수 있으므로, 백트래킹할 때 감시 영역을 원래대로 돌려놓는 작업에 주의를 기울일 필요가 있다.

# 북 동 남 서
dRow = [-1,0,1,0]
dCol = [0,1,0,-1]

n,m = map(int,input().split())
board = []
cam_loc = []
for row in range(n):
    li = []
    for col,v in enumerate(map(int,input().split())):
        if 1 <= v <= 5:
            cam_loc.append((row,col))
        li.append(v)
    board.append(li)
loc_len = len(cam_loc)


# 북 기준, 방향 인덱스
cams = [[],[0],[0,2],[0,1],[0,1,3],[0,1,2,3]]


def draw(d,_row,_col):
    _trace = []
    while 0 <= _row+dRow[d] < n and 0 <= _col+dCol[d] < m:
        _row += dRow[d]
        _col += dCol[d]
        if board[_row][_col] == 6:
            break
        elif board[_row][_col] == 0:
            _trace.append((_row, _col))
            board[_row][_col] = 9
    return _trace


def count_zeros():
    result = 0
    for row in range(n):
        for col in range(m):
            if board[row][col] == 0:
                result += 1
    return result


def dfs(idx):
    global answer
    if idx == loc_len:
        answer = min(answer,count_zeros())
        return
    row,col = cam_loc[idx]
    cam_num = board[row][col]
    for i in range(4):
        trace = []
        for d in map(lambda x : (x+i) % 4, cams[cam_num]):
            trace += draw(d,row,col)
        dfs(idx+1)
        for _row,_col in trace:
            board[_row][_col] = 0


answer = int(1e9)
dfs(0)
print(answer)

풀이 2

cctv의 최대개수가 8개밖에 안되므로, cctv의 좌표를 리스트에 넣어놓고 백트래킹으로 순회하며 모든 cctv의 감시영역을 펼쳤을 때 사각지대가 몇개 생기는지 확인하면 된다. 표시했던 감시영역을 다시 빈칸으로 되돌리기 위해 리스트에 표시했던 좌표를 넣어놓고 재귀 호출이 종료되면 빈칸으로 되돌리도록 한다.

# 북 서 남 동
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]
cctv = [
    [],
    [0],
    [0,2],
    [0,1],
    [0,1,2],
    [0,1,2,3]
]

N,M = map(int,input().split())
# 0:빈칸, 1~5:카메라, 6:벽, 9:감시영역
board = [[6]*(M+2) for row in range(N+2)]
locs = []
dirs = []
for i in range(1,N+1):
    for j,v in enumerate(map(int,input().split())):
        board[i][j+1] = v
        if 1 <= v <= 5:
            locs.append((v, i, j+1))
            dirs.append([*cctv[v]])


def get_answer(idx):
    global answer
    if idx > len(locs)-1:
        result = sum(map(lambda x : x.count(0),board))
        answer = min(answer,result)
        return
    # idx 카메라 90도씩 회전
    for _ in range(4):
        i, x, y = locs[idx]
        cache = []
        # 감시영역 표시
        for dir in dirs[idx]:
            nx,ny = x+dRow[dir],y+dCol[dir]
            while board[nx][ny] != 6:
                if board[nx][ny] == 0:
                    cache.append((nx,ny))
                    board[nx][ny] = 9
                nx,ny = nx+dRow[dir],ny+dCol[dir]
        # 재귀호출
        get_answer(idx+1)
        # 감시영역 지우기
        for row,col in cache:
            board[row][col] = 0
        # 90도 회전
        dirs[idx] = list(map(lambda x : (x+1)%4,dirs[idx]))


answer = int(1e9)
get_answer(0)
print(answer)