[BOJ] 파이썬 15683번_감시

문제링크

풀이

import sys
from itertools import *

input = lambda: sys.stdin.readline().strip()

up = (-1, 0)
right = (0, 1)
left = (0, -1)
down = (1, 0)

cam_1 = [[right], [down], [left], [up]]

cam_2 = [(right, left), (down, up), (right, left), (down, up)]

cam_3 = [(up, right), (right, down), (down, left), (left, up)]

cam_4 = [(up, right, left), (up, right, down), (right, down, left), (down, left, up)]

cam_5 = [(up, right, left, down), (up, right, left, down), (up, right, left, down), (up, right, left, down)]

cam_info = [[], cam_1, cam_2, cam_3, cam_4, cam_5]

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


def inRange(y_, x_):
    return 0 <= y_ < n and 0 <= x_ < m


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

cams = []
count = 0
for y in range(n):
    for x in range(m):
        if board_origin[y][x] in [1, 2, 3, 4, 5]:
            cams.append((y, x, board_origin[y][x]))
            count += 1
        if board_origin[y][x] == 0:
            count += 1

iters = product([0,1,2,3], repeat=len(cams))

min_ = count



def trav(cam,board):
    global min_

    if cam == len(cams):
        cnt= 0
        for y in range(n):
            for x in range(m):
                if board[y][x] == 0:
                    cnt += 1
        min_ = min(cnt, min_)

        return

    else:
        y, x, type = cams[cam]
        board_ = [item[:] for item in board]

        for i in range(4):
            directions = cam_info[type][i]
            for direction in directions:
                y_ = y
                x_ = x
                while True:
                    y_ = y_ + direction[0]
                    x_ = x_ + direction[1]

                    if inRange(y_,x_) and board_[y_][x_] != 6:
                        board_[y_][x_] = 9
                    else:
                        break
            trav(cam + 1, board_)
            board_ = [item[:] for item in board]


trav(0, board_origin)
print(min_)

백트래킹 문제임이 자명하다. 감시 카메라의 감시 범위의 방향을 편의를 위해 리스트에 저장한다.

먼저 전체 board를 순회하며 감시카메라 정보를 저장한다. 이후 모든 감시카메라의 모든 감시 방향에 대하여 백트랙킹을 실시했고, 각 가능한 경우의 수마다 0의 수(사각지대의 수) 를 계산했다.

++ 감시카메라가 없는 경우의 예외를 처리해주니 정답

++ iteretools의 permutation 기능을 써먹어버릇 하기 위해 한번 더 풀었다.

import sys
from itertools import *

input = lambda: sys.stdin.readline().strip()

up = (-1, 0)
right = (0, 1)
left = (0, -1)
down = (1, 0)

cam_1 = [[right], [down], [left], [up]]

cam_2 = [(right, left), (down, up), (right, left), (down, up)]

cam_3 = [(up, right), (right, down), (down, left), (left, up)]

cam_4 = [(up, right, left), (up, right, down), (right, down, left), (down, left, up)]

cam_5 = [(up, right, left, down), (up, right, left, down), (up, right, left, down), (up, right, left, down)]

cam_info = [[], cam_1, cam_2, cam_3, cam_4, cam_5]

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


def inRange(y_, x_):
    return 0 <= y_ < n and 0 <= x_ < m


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

cams = []
count = 0
for y in range(n):
    for x in range(m):
        if board_origin[y][x] in [1, 2, 3, 4, 5]:
            cams.append((y, x, board_origin[y][x]))
            count += 1
        if board_origin[y][x] == 0:
            count += 1

iters = product([0,1,2,3], repeat=len(cams))

ans = 0
min_ = count
for iter in iters:
    board = [item[:] for item in board_origin]
    for i in range(len(cams)):
        y, x, type = cams[i]

        rotation = int(iter[i])
        directions = cam_info[type][rotation]

        for direction in directions:
            y_ = y
            x_ = x

            while inRange(y_, x_):
                if board_origin[y_][x_] == 6:
                    break

                board[y_][x_] = 9

                y_ += direction[0]
                x_ += direction[1]

    cnt = 0
    for y in range(n):
        for x in range(m):

            if board[y][x] == 0:
                cnt += 1

    min_ = min(cnt, min_)

print(min_)

백트랙킹 과정이 없어지니 확실히 코드가 간소화 된 느낌이다.