0519_백준 15683번: 감시 / 브루트 포스 알고리즘

[문제 접근]

- 모든 경우의 수를 대입해보는 브루트 포스(Brute Force) 알고리즘 문제.

- dfs로 완전탐색하는 코드 구현, 효율이 굉장히 낮아 pypy로 제출하여 통과함.

- cctv 종류마다 탐색할 수 있는 모든 방향을 리스트에 담아 확인함.

- 모든 경우의 수에서 탐색하며 감시가 가능한 영역을 표시하고 사각지대의 최소값을 확인해야 하기 때문에, deepcopy 배열을 활용함.

[코드 구현]

from copy import deepcopy
import sys

# 감시 가능 영역 표시하기 -> 영역 표시는 copy 배열에
def office(x, y, temp, d):
    for i in d:
        nx, ny = x, y
        while True:
            nx += dx[i]
            ny += dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if temp[nx][ny] == 6:
                    break
                elif temp[nx][ny] == 0:
                    temp[nx][ny] = '#'
            else:
                break

# 깊이우선탐색으로 사각지대의 최소 구하기
def dfs(arr, cnt):
    global min_v
    temp = deepcopy(arr)
    if cnt == cctv_cnt:
        res = 0
        for i in range(n):
            res += temp[i].count(0)
        min_v = min(min_v, res)
        return
    x, y, cctv = cctv_lst[cnt]
    for d in directions[cctv]:
        # 유효 방향은 모두 탐색
        office(x, y, temp, d)
        dfs(temp, cnt+1)
        # copy 배열 복구
        temp = deepcopy(arr)

input = sys.stdin.readline
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# 하 상 우 좌
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
# 1~5번까지 가능한 방향 정의
directions = [
    [],
    [[0],[1],[2],[3]],
    [[0,1],[2,3]],
    [[3,0], [0, 2], [2, 1], [1, 3]],
    [[1,3,0],[3,0,2],[0,2,1],[2,1,3]],
    [[0, 1, 2, 3]]
    ]

min_v = 100000000
cctv_lst = []
cctv_cnt = 0

# cctv 위치와 개수 저장
for i in range(n):
    for j in range(m):
        if arr[i][j] != 0 and arr[i][j] != 6:
            cctv_lst.append([i, j, arr[i][j]])
            cctv_cnt += 1

dfs(arr, 0)
print(min_v)

[문제 출처]

백준 15683번 : 감시 (https://www.acmicpc.net/problem/15683)

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

15683번: 감시