[백준/Python] 15683. 감시 - 4진법 이용하기

Choi Jimin·2023년 10월 11일

백준(BOJ)

목록 보기

15/28

📄 문제

백준
난이도 : Gold 4
문제 제목 : 감시

✏️ 풀이 1

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
matrix_org = [list(map(int, input().split())) for _ in range(n)]
matrix_upd = [list(row) for row in matrix_org]
cctv_dirs = deque()   # 모든 방향 조합을 담는 큐
cctv_nums = 0
cctv_lst = []
for i in range(n):
    for j in range(m):
        if matrix_org[i][j] != 0 and matrix_org[i][j] != 6:
            cctv_nums += 1
            cctv_lst.append([i, j])

def get_dirs():
    # cctv는 4방향을 볼 수 있으니 나올 수 있는 cctv 방향 조합 수는 (4 ** k - 1)개
    for i in range(4 ** cctv_nums):
        # cctv 개수만큼의 자릿수가 나와야 함
        tmp = deque()
        for _ in range(cctv_nums):
            tmp.appendleft(i % 4)
            i //= 4
        cctv_dirs.append(tmp)

# cctv가 볼 수 있는 칸은 7로 마킹
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
def upd(y, x, dir):
    while True:
        y += dy[dir]
        x += dx[dir]
        if y < 0 or x < 0 or y >= n or x >= m:
            return
        if matrix_upd[y][x] == 6:
            return
        if matrix_upd[y][x] != 0:
            continue
        matrix_upd[y][x] = 7


get_dirs()
result = n * m
for d in cctv_dirs:
    for i in range(cctv_nums):
        current_row = cctv_lst[i][0]
        current_col = cctv_lst[i][1]
        if matrix_upd[current_row][current_col] == 1:
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i])
        if matrix_upd[current_row][current_col] == 2:
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i] % 2)
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i] % 2 + 2)
        if matrix_upd[current_row][current_col] == 3:
            set_d = d[i] + 1 if d[i] < 3 else 0
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i])
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d)
        if matrix_upd[current_row][current_col] == 4:
            tmp = {0, 1, 2, 3}
            tmp.remove(d[i])
            set_d = list(tmp)
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d[0])
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d[1])
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d[2])
        if matrix_upd[current_row][current_col] == 5:
            upd(cctv_lst[i][0], cctv_lst[i][1], 0)
            upd(cctv_lst[i][0], cctv_lst[i][1], 1)
            upd(cctv_lst[i][0], cctv_lst[i][1], 2)
            upd(cctv_lst[i][0], cctv_lst[i][1], 3)

    # 빈 칸 수 세기
    count = 0
    for row in matrix_upd:
        for col in row:
            count += 1 if col == 0 else 0
    result = min(count, result)

    matrix_upd = [list(row) for row in matrix_org]

print(result)

✅ 풀이 한줄 설명:
1. 각 cctv의 방향 정하기 - 💫 4진법 이용하기
2. 정한 방향에 대해서 사각 지대의 크기 구하기

✅ 풀이 자세한 설명:
나올 수 있는 cctv들의 방향 조합들을 먼저 구해야 한다. 백트래킹으로도 풀 수 있지만, 이 문제의 경우 4진법을 이용할 수 있다. 이 포스팅에서는 4진법을 이용할 것이고, 자세한 방법은 아래를 참고바란다. 만약 백트래킹으로 푸는 것에 감이 안온다면 'BOJ. N과 M (3)' 문제를 먼저 풀어보자.

가능한 모든 방향 조합을 구한 후에는, 조합마다 감시되는 칸을 모두 마킹하여 사각지대를 카운팅하면 된다.

🍎 1. 각 cctv의 방향 정하기
각 번호의 cctv를 변수라고 둘 때,

변수들이 가질 수 있는 값이 여러개
모든 조합을 확인하고 싶은 상황
변수들끼리 독립적

위 세 가지가 충족될 경우, 백트래킹이 아닌 진법을 이용해서 모든 조합을 얻을 수 있다. 이 문제의 경우 가능한 방향 종류가 4개이니 4진법을 사용한다.

예를 들어 1번 카메라가 3개일 때 0~63까지의 수를 4진법으로 나타낼 수 있다. 각각의 자리를 각 카메라의 방향에 대입하면 되는데, 예를 들어 39의 경우 4진수로 213이니 방향을 (2, 1, 3)으로 둘 수 있다.

수를 4진법으로 나타내는 방법은 '4를 나눈 나머지를 빼내고 4로 나누는 것을 반복'하는 것임에 유의하여 모든 방향 조합을 구하는 함수를 작성하면 다음과 같다.

# 모든 방향 조합을 담는 리스트
cctv_dirs = []
cctv_nums = 3

def get_dirs():
    # cctv는 4방향을 볼 수 있으니 나올 수 있는 cctv 방향 조합 수는 (4 ** k - 1)개
    for i in range(4 ** cctv_nums):
        tmp = deque()
        # cctv 개수만큼의 자릿수가 나와야 함
        for _ in range(cctv_nums):
            tmp.appendleft(i % 4)
            i //= 4
        cctv_dirs.append(tmp)

➕ 물론 위와 같이 작성하면 2번과 5번 cctv로 인해 중복되는 방향 조합이 생길 수 있다. 그러나 예외 처리가 더욱 품이 크기 때문에 해당 중복은 무시하기로 한다.

🍎 2. 정한 방향에 대해서 사각 지대의 크기 구하기
방향 조합마다 '각 cctv가 볼 수 있는 칸들에 마킹을 한 후, 마킹되지 않은 칸 수 세기'를 반복하며 최솟값을 구한다.

# cctv가 볼 수 있는 칸을 7로 마킹하는 함수
dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
def upd(y, x, dir):
    while True:
        y += dy[dir]
        x += dx[dir]
        if y < 0 or x < 0 or y >= n or x >= m:
            return
        if matrix_upd[y][x] == 6:
            return
        if matrix_upd[y][x] != 0:
            continue
        matrix_upd[y][x] = 7

# 마킹되지 않은 칸의 수 구하기 (가능한 방향 조합 별로)
for d in cctv_dirs:
    for i in range(cctv_nums):
        current_row = cctv_lst[i][0]
        current_col = cctv_lst[i][1]
        # 카메라 종류에 따라 감시 가능 칸 마킹
        if matrix_upd[current_row][current_col] == 1:
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i])
        if matrix_upd[current_row][current_col] == 2:
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i] % 2)
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i] % 2 + 2)
        if matrix_upd[current_row][current_col] == 3:
            set_d = d[i] + 1 if d[i] < 3 else 0
            upd(cctv_lst[i][0], cctv_lst[i][1], d[i])
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d)
        if matrix_upd[current_row][current_col] == 4:
            tmp = {0, 1, 2, 3}
            tmp.remove(d[i])
            set_d = list(tmp)
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d[0])
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d[1])
            upd(cctv_lst[i][0], cctv_lst[i][1], set_d[2])
        if matrix_upd[current_row][current_col] == 5:
            upd(cctv_lst[i][0], cctv_lst[i][1], 0)
            upd(cctv_lst[i][0], cctv_lst[i][1], 1)
            upd(cctv_lst[i][0], cctv_lst[i][1], 2)
            upd(cctv_lst[i][0], cctv_lst[i][1], 3)

    # 빈 칸 수 세기
    count = 0
    for row in matrix_upd:
        for col in row:
            count += 1 if col == 0 else 0
    result = min(count, result)

	# 다음 조합에 대한 마킹을 위해 matrix_upd 초기화
    matrix_upd = [list(row) for row in matrix_org]