감시 백준 15683번 구현

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

문제 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 ‘#’로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔	왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

사진은 따로 퍼오지 않았습니다. 이번 문제도 조건에 따라 CCTV의 감시 구역을 구하고 가장 많은 구역을 감시하는 경우를 찾으면 됩니다. 그리고 이런 많은 조건속에서 하나를 구해야하는 문제는 주로 DFS로 풀게 됩니다. 저도 많은 문제를 접하다보니 대충 이거는 어떻게 풀면 되겠다고 감이 오네요

n,m = map(int,input().split())
graph_list = []
camera_list = []
for i in range(n):
    graph_list.append(list(map(int,input().split())))
    for j in range(m):
        if graph_list[i][j] != 0 and graph_list[i][j] != 6:
            camera_list.append([graph_list[i][j],i,j])

dx = [1,0,-1,0]
dy = [0,1,0,-1]
mode = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]],
]

먼저 지도를 입력받고 cctv의위치를 기록한 다음 cctv가 볼 수 있는 모드를 기록합시다. 당연히 mode[0]을 비워두는 이유는 인덱스 때문입니다.

1번 카메라의 경우 1방향으로 4가지, 2번 카메라는 2방향으로 2가지 이렇게 총 5가지 카메라가 있고 각 카메라가 감시할 수 있는 방향은 이렇게 명시를 해줍시다.

def dfs(depth, arr):
    global min_value
    if depth == len(camera_list):
        count = 0
        for i in range(n):
            count += arr[i].count(0)
        min_value = min(min_value, count)
        return
    temp = copy.deepcopy(arr)
    cctv_num, x, y = camera_list[depth]
    for i in mode[cctv_num]:
        fill(temp, i, x, y)
        dfs(depth+1, temp)
        temp = copy.deepcopy(arr)

일단 DFS함수부터 살펴보겠습니다. 파라미터는 depth와 arr배열이 들어가게 되는데 카메라의 개수만큼 dfs가 돌기 때문에 이를 체크하기 위함입니다.

우리가 비어있는 공간(벽, 카메라, 감시되지 않는 구역)의 경우 0으로 지정을 했습니다. 카메라 만큼 돌렸을때 0의 개수(사각지대)의 개수를 세고 기존의 최저값 min_value와 비교를 하고 더 작은 값을 갱신합니다.

아직 감시해야할 카메라가 남을 경우 구하러 가봅시다. 일단 우리는 앞에서 카메라는 리스트에 저장을 했습니다.

카메라 번호와 카메라의 위치를 구하고 각 카메라 모드에 따라서 동작을 반복합니다. 그러면 여기서 fill 함수를 한번 살펴봅시다.

def fill(board, mm, x, y):
    for i in mm:
        nx = x
        ny = y
        while True:
            nx += dx[i]
            ny += dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                break
            if board[nx][ny] == 6:
                break
            elif board[nx][ny] == 0:
                board[nx][ny] = 7

인자는 지도 배열, 카메라 번호, 카메라의 위치가 됩니다. 카메라의 번호는 정확히 감시하는 곳이 됩니다.

그러니까 만약 2번 카메라가 들어 갔다면 첫번째 for문에는 0,2 두번째에는1,3으로 감시할 수 있는 방향으로 쭉 나가게 됩니다. 여기서 for문 한번당 감시하는 방향이 되고 while에서 감시할 수 있는 곳 까지 감시를 하게 되는데 감시를 할 수 없는 곳을 만나면 (6)이라면 빠져나오고 아니라면 7로 변경을 해줍니다. 카메라의 경우 통과할 수 있다고 했으니 별다른 체크를 하지 않아도 됩니다.

이렇게 각 카메라가 감시할 수 있는 모든 경우를 체크를 하고 다음 dfs로 넘어가게 됩니다. 그러면 마지막(최대깊이) 까지 도달한 값중에서 최소 값을 출력해서 돌려주게 됩니다.