[BOJ] 감시 - BFS, Recursive

15683 감시 골드5

cctv가 8개 이하이기 때문에 모든 가능성을 확인하는 BFS 로 문제풀이를 하였다.

import sys
input = sys.stdin.readline

nheight, nwidth = list(map(int, input().split()))
board = []
for _ in range(nheight):
    board.append(list(map(int, input().split())))

cctv = []
cctv5 = [] # 5번 cctv

allcc = set() # 모든 cctv의 좌표를 저장

for j in range(nheight):
    for i in range(nwidth):
        if 0 < board[j][i] < 5:
            cctv.append((board[j][i], j, i))
            allcc.add((j,i))
        elif board[j][i] == 5:
            cctv5.append((j,i))
            allcc.add((j,i))
# print(cctv)

def watchTop(y,x):
    res = set()
    j = y
    while j + 1 < nheight and board[j + 1][x] != 6:
        j += 1
        if (j,x) not in allcc:
            res.add((j,x))  # 감시 받는 영역 표시
    return res
def watchBottom(y,x):
    res = set()
    j = y
    while j - 1 >= 0 and board[j - 1][x] != 6:
        j -= 1
        if (j,x) not in allcc:
            res.add((j,x))  # 감시 받는 영역 표시
    return res
def watchRight(y,x):
    res = set()
    j = x
    while j + 1 < nwidth and board[y][j + 1] != 6:
        j += 1
        if (y,j) not in allcc:
            res.add((y,j))
    return res
def watchLeft(y,x):
    res = set()
    j = x
    while j - 1 >= 0 and board[y][j - 1] != 6:
        j -= 1
        if (y, j) not in allcc:
            res.add((y, j))
    return res

watched = set()
for c5 in cctv5: # 5 번 cctv 먼저 처리
    y,x = c5
    watched.update(watchTop(y,x))
    watched.update(watchBottom(y,x))
    watched.update(watchRight(y,x))
    watched.update(watchLeft(y,x))

watch = []
watch.append([(watchLeft,),(watchRight,),(watchTop,),(watchBottom,)])
watch.append([(watchLeft, watchRight), (watchTop, watchBottom)])
watch.append([(watchTop, watchRight),(watchRight, watchBottom), (watchBottom, watchLeft), (watchLeft, watchTop)])
watch.append([(watchTop,watchRight, watchLeft),(watchTop, watchRight, watchBottom),(watchRight, watchBottom, watchLeft), (watchBottom, watchLeft, watchTop)])

answer = 0
def recursiveWatch(idx, wcd): # idx : 확인할 cctv num, wcd : 현재 감시받고 있는 영역들
    if idx >= len(cctv):
        return len(wcd)
    c_num, y, x = cctv[idx]
    res = 0
    for watcher in watch[c_num-1]:
        newWatched = set()
        for func in watcher:
            newWatched.update(func(y,x))
        res = max(res, recursiveWatch(idx + 1, wcd | newWatched))
    return res
answer = recursiveWatch(0,watched)
zeros = sum(board,[]).count(0)
print(zeros - answer)

---

watchTop, watchBottom, watchRight, watchLeft 들은 y,x 좌표를 기준으로 위쪽, 아래쪽, 또는 왼쪽 오른쪽에 cctv가 감시할 수 있는 영역들을 return 한다.

---

5 번 cctv는 모든 방향을 다 탐색하므로, 가능한 경우의 수가 한 개 뿐이다. 바로 watched 에 추가해준다.

---

watch = []
watch.append([(watchLeft,),(watchRight,),(watchTop,),(watchBottom,)])
watch.append([(watchLeft, watchRight), (watchTop, watchBottom)])
watch.append([(watchTop, watchRight),(watchRight, watchBottom), (watchBottom, watchLeft), (watchLeft, watchTop)])
watch.append([(watchTop,watchRight, watchLeft),(watchTop, watchRight, watchBottom),(watchRight, watchBottom, watchLeft), (watchBottom, watchLeft, watchTop)])

watch[i] 는 i+1 번 cctv가 볼 수 있는 경우의 수 들을 배열로 가진다.
예를들어 watch[1] 은 2번 cctv가 볼 수 있는 경우의 수이다. 2번 cctv는 위 아래 또는 왼쪽 오른쪽을 한 번에 볼 수 있으므로 [(watchLeft, watchRight),(watchTop,watchBottom)] 이다.

---

answer = 0
def recursiveWatch(idx, wcd): # idx : 확인할 cctv num, wcd : 현재 감시받고 있는 영역들
    if idx >= len(cctv):
        return len(wcd)
    c_num, y, x = cctv[idx]
    res = 0
    for watcher in watch[c_num-1]:
        newWatched = set()
        for func in watcher:
            newWatched.update(func(y,x))
        res = max(res, recursiveWatch(idx + 1, wcd | newWatched))
    return res
answer = recursiveWatch(0,watched)
zeros = sum(board,[]).count(0)
print(zeros - answer)

하나씩 확인해준다.
recursiveWatch 는 가장 큰 wcd(감시받고 있는 영역의 수) 의 값을 return 하므로 전체 0의 개수인 zeros 에서 그 수만큼을 제거하면 가장 적은 안전영역의 수가 된다.