[백준] 15683번 감시 파이썬

NxM 크기의 사무실.

K개의 CCTV (5종류 / 1번 CCTV는 한 쪽 방향만 감시, 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향, 3번은 직각 방향, 4번은 세 방향, 5번은 네 방향)

CCTV는 벽을 통과할 수 없으며, CCTV가 감시할 수 없는 영역은 사각지대.

CCTV는 항상 90도 방향으로 회전할 수 있으며, 감시하려는 방향이 가로 또는 세로 방향임.

 

- 입력

1줄 : 사무실의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 8)

2~N줄 : 사무실 각 칸의 정보 (0 : 빈칸, 6 : 벽, 1~5 : CCTV)   *CCTV는 8개 이하

 

- 출력

사각 지대의 최소 크기

 

고민) dfs에서 재귀로 돌리면서 확인하는 걸텐데.. 해당 가로 또는 세로를 어떻게 변경해주지? 벽인 것도 확인해줘야 하는데...

n, m = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(n)]

#남, 북, 서, 동
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
x, y = 0, 0

def dfs(office):
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]

    if not (0 <= nx < m and 0 <= ny < n):
      continue

    x, y = nx, ny
    if office[nx][ny] == 6 or office[nx][ny] == "#":
      continue

    if office[nx][ny] == 1:
      office[x:][y] = "#"

    if office[nx][ny] == 2:
      office[x:][y]

    if office[nx][ny] == 3:
      office[x][y]

    if office[nx][ny] == 4:
      office[x][y]

    if office[nx][ny] == 5:
      office[x][y]
      
def getResult(office):
  cnt = 0
  for i in range(m):
    for j in range(n):
      if office[i][j] == 0:
        cnt += 1
  return cnt

temp = office[:]
dfs(temp)
min(0, getResult(temp))

 

15683번 감시

해답)  CCTV의 5개 종류를 mode로 정의해두고 사용한다...! cctv 리스트에 cctv의 종류와 위치 i, j를 담는다. 그리고 dfs함수를 재귀로 사용해서 사각지대의 최솟값을 찾는다. dfs에서 cctv를 모두 확인하기 전에는 if depth == len(cctv)에 걸리지 않으므로 temp에 ar를 복사하고 temp에 접근하여 값을 변경해준다. 해당 temp는 fill함수의 매개변수로 대입되며, fill함수 안에서 범위 안에 있으면서 6인 벽이 아닌 0의 칸이면 7을 대입하여 감시되는 공감임으로 표시한다. 이를 재귀로 반복하는데 fill함수 호출 뒤에는 dfs에 들어가는 depth와 arr 배개변수의 값을 업데이트해주는 것이 필요하고, temp도 다시 새롭게 복사해서 사용해야 함을 주의한다. 

import copy
n, m = map(int, input().split())
cctv = []
graph = []
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]],
]

# 북 - 동 - 남 - 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for i in range(n):
    data = list(map(int, input().split()))
    graph.append(data)
    for j in range(m):
        if data[j] in [1, 2, 3, 4, 5]:
            cctv.append([data[j], i, j])

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

def dfs(depth, arr):
    global min_value

    if depth == len(cctv):
        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 = cctv[depth]
    for i in mode[cctv_num]:
        fill(temp, i, x, y)
        dfs(depth+1, temp)
        temp = copy.deepcopy(arr)


min_value = int(1e9)
dfs(0, graph)
print(min_value)

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

15683번: 감시

참고 : https://developer-ellen.tistory.com/53

BOJ - 감시 15683번 (python)