[BOJ] 15683번 감시 (Python) [삼성 SW 역량 테스트 기출 문제]

문제

https://www.acmicpc.net/problem/15683

풀이

CCTV가 CCTV를 통과한다는 문제의 부분을 정확히 읽고 이해하지 않고 넘어가서 삽질했다. 무조건 문제를 정확히 이해하고 넘어가자. 문제 읽는데 5분 더 투자하는게 30분 삽질을 없애준다. 특히, 예시가 주어진 경우 그 예시를 무조건 정확히 이해하고 넘어가야 한다.

틀렸을 때 반례를 스스로 찾기가 어려워서 계속 게시판의 반례를 찾게되는데, 스스로 찾는 연습이 필요할 듯. 일단 틀렸으면 문제에서 잘못이해한 부분이 없는지 체크하자 반례부터 찾지말고

이전 문제들에 비해 코드레벨로 빨리 손이 갔다. 무조건 손코딩으로 정리한번 하고 들어가자. 아니면 진짜 우당탕탕된다.

우당탕탕 풀어서 굉장히 더럽게 풀었고, 변수명도 명확하지 않다. 변수명 최대한 직관적으로 지어야지 안그러면 문제 푸는 내내 헷갈린다.

from collections import OrderedDict  # 버전 이슈 없애기 위해
from itertools import product
from copy import deepcopy

UP, DOWN, LEFT, RIGHT = "UP", "DOWN", "LEFT", "RIGHT"
DX_DY = {UP: (-1, 0), DOWN: (1, 0), LEFT: (0, -1), RIGHT: (0, 1)}
WATCHABLE = "X"

CCTV_DIR_CANDIDATES = [
    None,
    [(UP, ), (DOWN, ), (LEFT, ), (RIGHT, )],  # 1번 CCTV
    [(UP, DOWN), (LEFT, RIGHT)],  # 2번 CCTV
    [(UP, RIGHT), (RIGHT, DOWN), (DOWN, LEFT), (LEFT, UP)],  # 3번 CCTV
    [(UP, DOWN, LEFT), (UP, DOWN, RIGHT), (UP, LEFT, RIGHT),
     (DOWN, LEFT, RIGHT)],  # 4번 CCTV
    [(UP, DOWN, LEFT, RIGHT)],  # 5번 CCTV
]


def get_cctv_dir_product(cctv_categories):
    product_list = []
    for cctv_category in cctv_categories:
        product_list.append(CCTV_DIR_CANDIDATES[cctv_category])
    return list(product(*product_list))


def is_valid(x, y, graph):
    # 범위안에 있고, 빈 곳이거나 이미 감시대상인 곳
    if 0 <= x < N and 0 <= y < M and graph[x][y] != 6:  # CCTV는 통과 가능
        return True
    return False


def fill(x, y, directions, graph):
    for direction in directions:
        copied_x, copied_y = x, y
        dx, dy = DX_DY[direction]
        while is_valid(copied_x + dx, copied_y + dy, graph):
            if graph[copied_x + dx][copied_y + dy] == 0: # cctv 아니면
                  graph[copied_x + dx][copied_y + dy] = WATCHABLE
            copied_x, copied_y = copied_x + dx, copied_y + dy


N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

cctv_info = OrderedDict()
for i in range(N):
    for j in range(M):
        if 1 <= graph[i][j] <= 5:  #CCTV
            cctv_info[(i, j)] = graph[i][j]

cctv_directions = get_cctv_dir_product(cctv_info.values())  # 4**8
ans = float('inf')
for cctv_direction in cctv_directions:
    # {(1, 1): (0, 1), (3, 4): (0, 1), (5, 5): (0, 1, 2, 3)}
    dir_match = {
        key: dir
        for key, dir in zip(cctv_info.keys(), cctv_direction)
    }
    copied_graph = deepcopy(graph)  # 원본 초기화
    for i in range(N):
        for j in range(M):
            if (i, j) in dir_match:
                directions = dir_match[(i, j)]
                # 채우기 처리
                fill(i, j, directions, copied_graph)

    # 사각지대 수 측정해서 갱신 (8*8)
    empty_count = 0
    for i in range(N):
        for j in range(M):
            if copied_graph[i][j] == 0:
                empty_count += 1
    ans = min(ans, empty_count)
    # if ans == 9:
    #   for l in copied_graph:
    #     print(l)

print(ans)