🥚문제링크

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

• 구현
• 브루트포스 알고리즘
• 시뮬레이션

---

🍳코드

import sys
from collections import deque
input = sys.stdin.readline

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


def cctv(arr, r, c, dx, dy):
    new_arr = [row[:] for row in arr]
    # dx = [0, 0, -1, 1]
    # dy = [-1, 1, 0, 0]
    for i in range(len(dx)):
        new_r = r
        new_c = c
        while 0 <= new_r + dx[i] < N and 0 <= new_c + dy[i] < M:
            new_r += dx[i]
            new_c += dy[i]
            # 빈칸이라면
            if new_arr[new_r][new_c] == 0:
                new_arr[new_r][new_c] = -1  # -1을 감시하는 구역으로 표시
            # 다른 cctv라면
            elif 0 <= new_arr[new_r][new_c] < 6:
                continue  # 통과
            # 벽이라면
            elif new_arr[new_r][new_c] == 6:
                break  # 중단
    return new_arr


def solve(arr, q):
    global min_area

    # q가 비어있을 경우
    if len(q) == 0:
        tmp_area = 0
        for r in range(N):
            for c in range(M):
                if arr[r][c] == 0:
                    tmp_area += 1
        min_area = min(min_area, tmp_area)
        return

    r, c = q.popleft()
    if arr[r][c] == 1:
        arr_left = cctv(arr, r, c, [0], [-1])
        arr_right = cctv(arr, r, c, [0], [1])
        arr_bottom = cctv(arr, r, c, [1], [0])
        arr_top = cctv(arr, r, c, [-1], [0])
        # recursion
        # q를 항상 deepcopy 해줘야 함에 유의
        solve(arr_left, deque([x for x in q]))
        solve(arr_right, deque([x for x in q]))
        solve(arr_bottom, deque([x for x in q]))
        solve(arr_top, deque([x for x in q]))

    elif arr[r][c] == 2:
        arr_left_right = cctv(arr, r, c, [0, 0], [-1, 1])
        arr_top_bottom = cctv(arr, r, c, [-1, 1], [0, 0])
        # recursion
        solve(arr_left_right, deque([x for x in q]))
        solve(arr_top_bottom, deque([x for x in q]))

    elif arr[r][c] == 3:
        arr_top_right = cctv(arr, r, c, [-1, 0], [0, 1])
        arr_right_bottom = cctv(arr, r, c, [0, 1], [1, 0])
        arr_bottom_left = cctv(arr, r, c, [1, 0], [0, -1])
        arr_left_top = cctv(arr, r, c, [0, -1], [-1, 0])
        # recursion
        solve(arr_top_right, deque([x for x in q]))
        solve(arr_right_bottom, deque([x for x in q]))
        solve(arr_bottom_left, deque([x for x in q]))
        solve(arr_left_top, deque([x for x in q]))

    elif arr[r][c] == 4:
        arr_not_bottom = cctv(arr, r, c, [-1, 0, 0], [0, 1, -1])
        arr_not_left = cctv(arr, r, c, [-1, 0, 1], [0, 1, 0])
        arr_not_top = cctv(arr, r, c, [0, 0, 1], [-1, 1, 0])
        arr_not_right = cctv(arr, r, c, [-1, 0, 1], [0, -1, 0])
        # recursion
        solve(arr_not_bottom, deque([x for x in q]))
        solve(arr_not_left, deque([x for x in q]))
        solve(arr_not_top, deque([x for x in q]))
        solve(arr_not_right, deque([x for x in q]))

    elif arr[r][c] == 5:
        new_arr = cctv(arr, r, c, [0, 0, -1, 1], [-1, 1, 0, 0])
        # recursion
        solve(new_arr, deque([x for x in q]))


# cctv의 좌표 저장
q = deque([])
for r in range(N):
    for c in range(M):
        if 0 < arr[r][c] < 6:
            q.append((r, c))

min_area = 64

solve(arr, q)
print(min_area)

---

🧂아이디어

구현

1. 세로크기와 가로크기를 각각 N, M에, 사무실 각 칸의 정보를 arr에 저장한다.

2. arr에서 cctv가 있는 곳의 좌표를 q에 저장한다.

3. arr과 q를 인자로 갖는 재귀함수 solve를 호출한다.
   • q가 비어있다면 arr의 사각지대 크기를 구한 뒤, min_area보다 작다면 갱신해주고 리턴한다.
   • q.popleft()를 통해 cctv의 좌표 하나를 빼낸다. cctv의 번호에 따라 row의 감시 방향인 dx, col의 감시 방향인 dy를 다르게 해주며 cctv(arr, r, c, dx, dy)함수를 호출하고, 감시할 수 있는 구역을 -1로 표시한 상태인 새로운 2차원 리스트를 리턴받는다.
   • 위에서 리턴받은 새로운 2차원 리스트와 q에 남아있는 다른 cctv의 좌표들을 deepcopy한 것을 인자로 삼는 재귀함수 solve를 호출한다.

4. 사각지대의 최소 크기인 min_area를 출력한다.

---

🧐 다른 버전

참고: https://www.acmicpc.net/source/15002633 (ydh2244님 코드)

import sys
import copy
input = sys.stdin.readline


def dfs(idx, arr):
    global min_area

    if idx == len(cctv):
        # 모든 cctv 완료
        current_area = sum([row.count(0) for row in arr])
        min_area = min(min_area, current_area)
        return

    r, c, cctv_mode = cctv[idx]

    for cctv_dirs in directions[cctv_mode]:
        new_arr = copy.deepcopy(arr)
        for i in cctv_dirs:
            nr = r
            nc = c
            while 0 <= nr < N and 0 <= nc < M:
                # 벽을 만나면
                if new_arr[nr][nc] == 6:
                    break
                if new_arr[nr][nc] == 0:
                    # 빈 공간이라면
                    new_arr[nr][nc] = -1  # 감시할 수 있음을 표시
                # 다른 cctv라면
                # update
                nr += dr[i]
                nc += dc[i]
        dfs(idx+1, new_arr)


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

dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]
# directions[i] = i번 cctv의 감시 방향들을 저장한 리스트
directions = [
    [],
    [[0], [1], [2], [3]],
    [[0, 1], [2, 3]],
    [[2, 1], [1, 3], [3, 0], [0, 2]],
    [[0, 1, 2], [1, 2, 3], [0, 1, 3], [0, 2, 3]],
    [[0, 1, 2, 3]]
]


min_area = M*N
cctv = []
for r in range(N):
    for c in range(M):
        if 1 <= arr[r][c] <= 5:
            # cctv가 있는 곳의 row, col, cctv번호를 추가
            cctv.append((r, c, arr[r][c]))

dfs(0, arr)
print(min_area)

• cctv별로 감시 방향을 저장한 리스트를 사용하는 것 배움