[백준 15683] 감시

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

15683번: 감시

---

접근

이 문제는 CCTV의 방향을 어떻게 설정할 것인지가 관건이었다. 각각의 CCTV에 따라 감시할 수 있는 방향을 딕셔너리 형태로 선언해주었다. 이후 CCTV의 개수만큼 DFS를 하여 해당 CCTV를 감시할 수 있는 방향을 모두 탐색할 수 있도록하였다.

 

결론적으로 CCTV의 방향을 어떻게 모델링할 것인지와 DFS를 통한 완전탐색으로 접근하였다.

 

구현

- CCTV의 위치와 번호를 cctv_list에 저장하였다. 각각의 탐색마다 picked가 가리키는 CCTV를 cctv_list에서 꺼낸다.

- 이를 활용하여 해당 CCTV로 감시할 수 있는 곳을 -1로 만든다.

- 이후 다음 CCTV로 감시할 수 있도록 재귀호출을 한다.

- 이때 해당 CCTV가 회전할 수 있는 모든 방향을 탐색할 수 있도록 한다.

- picked가 CCTV_SIZE가 된 것은 모든 CCTV에 대해 감시할 수 있는 범위를 모두 -1로 했다는 것이다.

- 따라서 0인 곳을 찾아 count를 증가시킨다.

def solve(board, picked):
    global answer
    if picked == CCTV_SIZE:
        count = 0
        for y in range(N):
            for x in range(M):
                if board[y][x] == 0:
                    count += 1
        answer = min(answer, count)
        return

    cctv_y, cctv_x, cctv_number = cctv_list[picked][0], cctv_list[picked][1], cctv_list[picked][2]


    copy_board = [[0 for _ in range(M)] for _ in range(N)]
    copy_map(board, copy_board)

    for i in range(len(cctv[cctv_number])):
        for j in range(len(cctv[cctv_number][i])):
            ny = cctv_y
            nx = cctv_x
            while True:
                ny += cctv[cctv_number][i][j][0]
                nx += cctv[cctv_number][i][j][1]
                if check_range(ny, nx) and copy_board[ny][nx] != 6:
                    copy_board[ny][nx] = -1
                else:
                    break
        solve(copy_board, picked+1)
        copy_map(board, copy_board)

---

전체 코드

import sys
input = sys.stdin.readline

# i->len(cctv[3]), j -> len(cctv[3][i]) -> i,j,0 or i,j,1
cctv = {
    1: [[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]],
    2: [[(0, 1), (0, -1)], [(1, 0), (-1, 0)]],
    3: [[(0, 1), (-1, 0)], [(0, -1), (-1, 0)], [(1, 0), (0, -1)], [(0, 1), (1, 0)]],
    4: [[(0, 1), (-1, 0), (0, -1)], [(-1, 0), (0, -1), (1, 0)], [(0, -1), (1, 0), (0, 1)], [(-1, 0), (0, 1), (1, 0)]],
    5: [[(0, 1), (0, -1), (1, 0), (-1, 0)]]
}

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < M)

def copy_map(board, copy_board):
    for i in range(N):
        for j in range(M):
            copy_board[i][j] = board[i][j]

def solve(board, picked):
    global answer
    if picked == CCTV_SIZE:
        count = 0
        for y in range(N):
            for x in range(M):
                if board[y][x] == 0:
                    count += 1
        answer = min(answer, count)
        return

    cctv_y, cctv_x, cctv_number = cctv_list[picked][0], cctv_list[picked][1], cctv_list[picked][2]


    copy_board = [[0 for _ in range(M)] for _ in range(N)]
    copy_map(board, copy_board)

    for i in range(len(cctv[cctv_number])):
        for j in range(len(cctv[cctv_number][i])):
            ny = cctv_y
            nx = cctv_x
            while True:
                ny += cctv[cctv_number][i][j][0]
                nx += cctv[cctv_number][i][j][1]
                if check_range(ny, nx) and copy_board[ny][nx] != 6:
                    copy_board[ny][nx] = -1
                else:
                    break
        solve(copy_board, picked+1)
        copy_map(board, copy_board)

N, M = map(int, input().split())
board = [list(map(int, input().split() )) for _ in range(N)]

cctv_list = []
for i in range(N):
    for j in range(M):
        if board[i][j] > 0 and board[i][j] < 6:
            cctv_list.append((i, j, board[i][j]))

answer = N * M
CCTV_SIZE = len(cctv_list)

solve(board, 0)
print(answer)