문제 링크

15683 - 감시

문제 설명

1×1크기의 정사각형으로 나누어져 있는 N*M크기의 사무실에 총 K개의 CCTV가 설치되어있다. cctv의 종류는 총 5개! 각 cctv는 다음과 같은 영역을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있고, 벽은 통과할 수 없다. 회전은 90도로 가능하고, 감시방향은 가로 또는 세로여야 한다. 사무실의 크기와 CCTV배치가 주어졌을때 사각지대의 최소 크기를 구하라.

문제 풀이

BFS를 안푼지 오래된거같아서 BFS로 풀어보았다. 사실 DFS로 탐색하고 이전 상태로 돌려주는 부분이 귀찮을거같아서,,
계속 deepcopy해서 먼가 메모리 효율성이 떨어지는거같은데,, 이 부분은 스터디에서 다른 분들 어떻게 풀었나 보고 개선해봐야겠음

import sys
import copy
from collections import deque

input = sys.stdin.readline

#상좌하우
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def in_bound(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

def check(num, board, d, x, y):
    nx, ny = x+dx[d], y+dy[d]
    while in_bound(nx, ny):
        if board[nx][ny] != 6:
            if board[nx][ny] == 0:
                board[nx][ny] = "#"
            nx, ny = nx+dx[d], ny+dy[d]
        else:
            break
    
    if num == 3 or num == 4 or num == 5:
        nx, ny = x+dx[(d+1)%4], y+dy[(d+1)%4]
        while in_bound(nx, ny):
            if board[nx][ny] != 6:
                if board[nx][ny] == 0:
                    board[nx][ny] = "#"
                nx, ny = nx+dx[(d+1)%4], ny+dy[(d+1)%4]
            else:
                break
    
    if num == 2 or num == 5:
        nx, ny = x+dx[(d+2)%4], y+dy[(d+2)%4]
        while in_bound(nx, ny):
            if board[nx][ny] != 6:
                if board[nx][ny] == 0:
                    board[nx][ny] = "#"
                nx, ny = nx+dx[(d+2)%4], ny+dy[(d+2)%4]
            else:
                break
    
    if num == 4 or num == 5:
        nx, ny = x+dx[(d+3)%4], y+dy[(d+3)%4]
        while in_bound(nx, ny):
            if board[nx][ny] != 6:
                if board[nx][ny] == 0:
                    board[nx][ny] = "#"
                nx, ny = nx+dx[(d+3)%4], ny+dy[(d+3)%4]
            else:
                break

def bfs(board, cctv):
    queue = deque([(board, cctv)])
    global minval
    while queue:
        b, c = queue.popleft()
        if not c:
            count = 0
            for i in range(len(b)):
                for j in range(len(b[0])):
                    if b[i][j] == 0:
                        count += 1
            minval = min(minval, count)
        else:
            cnum, x, y = c.popleft()
            if cnum in [1, 3, 4]:
                # 4방향에 대해 체크
                for i in range(4):
                    nb = copy.deepcopy(b)
                    nc = copy.deepcopy(c)
                    check(cnum, nb, i, x, y)
                    queue.append((nb, nc))
            elif cnum == 2:
                # 2방향에 대해 체크
                for i in range(2):
                    nb = copy.deepcopy(b)
                    nc = copy.deepcopy(c)
                    check(cnum, nb, i, x, y)
                    queue.append((nb, nc))
            else:
                # 한방향에 대해 체크
                nb = copy.deepcopy(b)
                nc = copy.deepcopy(c)
                check(cnum, nb, 0, x, y)
                queue.append((nb, nc))

N, M = map(int, input().split())
minval = N*M
board = []
cctv = deque()
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        if tmp[j] in range(1, 6):
            cctv.append((tmp[j], i, j))
    board.append(tmp)
bfs(board, cctv)
print(minval)

5번 카메라 체크하는 부분 위에꺼 막 복붙했더니 방향이 그냥 i로 들어가있어서 한참 런타임에러가 났다 ^_ㅠ
UnboundLocalError는 선언하지 않은 변수 썼을때 나는 에러,,