[BOJ] 15683번 감시 - Python

🥸 문제

15683번: 감시

 

---

🥳 해설 및 풀이

input size를 계산해보니 브루트 포스가 가능한 문제였고,

4^8(가능한 경우의 수) * board의 크기 (8 * 8) 정도가 최대 계산 빈도수 정도여서 완전탐색으로 진행할 수 있었다. 

전체 경우의 수(4가지 케이스 (동서남북) ** 8(CCTV의 최대 개수))를 어떻게 두면 좋을지 고민했는데, 

가능한 경우의 수를 그냥 숫자로 가정하고 4^len(cctv) 만큼 반복문을 돌려줬더니 편하게 계산할 수 있었다.

 

핵심은 아래처럼 curr 변수를 중복되지 않게 재조정 해주는 과정이다. (4가지 경우가 가능하니 4진법으로 이용하는 느낌)

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

# ...

for k in range(4^len(cctv))
    curr = k
    for i in range(len(cctv))
        d = curr % 4  # dx, dy에서의 방향 중 하나 선택
        
        # ... 계산
        
        curr //= 4  # 다음 경우의 수를 위한 curr 조정

 

 

---

🏈 완성 코드

n, m = map(int, input().split())

origin_board = [[0] * m for _ in range(n)]  # 최초에 입력받은 board를 저장할 변수
current_board = [[0] * m for _ in range(n)]  # 사각 지대의 개수를 세기 위해 사용할 변수

cctv = []  # cctv의 좌표를 저장할 변수

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

# -----------------------------------------------------------------------


def is_out_of_bound(x, y):  # Out Of Bounds 확인
    return x < 0 or x >= n or y < 0 or y >= m


# (x, y)에서 d 방향으로 벽을 만나기 전까지 방문하는 모든 빈칸을 7로 방문표시 해줌
def update_board(x, y, d):
    d %= 4
    while True:
        x += dx[d]
        y += dy[d]
        if is_out_of_bound(x, y) or current_board[x][y] == 6:
            return  # 벽을 만나거나 범위를 벗어났을 때는 탐색 중지
        if current_board[x][y] != 0:
            continue  # 해당 칸에 cctv가 있을 경우에는 넘어가기
        current_board[x][y] = 7  # 빈칸을 7로 덮음


def solution():
    min_size = 0  # 사각 지대의 최소 크기 (= 답)

    for i in range(n):
        row = list(map(int, input().split()))
        for j in range(m):
            origin_board[i][j] = row[j]
            if 1 <= origin_board[i][j] <= 5:
                cctv.append((i, j))
            if origin_board[i][j] == 0:
                min_size += 1

    # 4^(len(cctv)) 만큼 반복
    for k in range(4 ** (len(cctv))):
        # 일단 복사 (초기화 과정)
        for i in range(n):
            for j in range(m):
                current_board[i][j] = origin_board[i][j]

        curr = k
        for i in range(len(cctv)):
            x, y = cctv[i]
            d = curr % 4  # 0, 1, 2, 3 중 하나

            if origin_board[x][y] == 1:
                update_board(x, y, d)
            elif origin_board[x][y] == 2:
                update_board(x, y, d)
                update_board(x, y, d + 2)
            elif origin_board[x][y] == 3:
                update_board(x, y, d)
                update_board(x, y, d + 1)
            elif origin_board[x][y] == 4:
                update_board(x, y, d)
                update_board(x, y, d + 1)
                update_board(x, y, d + 2)
            else:
                update_board(x, y, d)
                update_board(x, y, d + 1)
                update_board(x, y, d + 2)
                update_board(x, y, d + 3)

            curr //= 4
        min_size = min(sum(current_board[i][j] == 0 for i in range(n) for j in range(m)), min_size)
    return min_size


print(solution())