[Python] 백준(BOJ):

문제

문제 설명

Startlink의 사무실은 NxM 크기의 직사각형을 1×1 크기의 정사각형으로 나눈 것으로 나타낼 수 있습니다.
사무실에는 총 K대의 CCTV가 설치되어 있으며, CCTV의 종류는 5가지입니다. 각각의 CCTV가 감시할 수 있는 방법은 다음과 같다.

#1 CCTV는 한 방향으로만 감시할 수 있습니다. 2번과 3번은 양방향 감시가 가능하며, 2번은 반대 방향, 3번은 직각 방향으로 감시해야 합니다. 4번은 3방향, 5번은 4방향 모니터링이 가능합니다.

• CCTV는 감시할 수 있는 방향으로 부서 전체를 감시할 수 있다. 사무실에 벽이 있는데 CCTV가 벽을 뚫지 못합니다.
  CCTV로 감시할 수 없는 영역을 사각지대라고 합니다.
• CCTV는 회전이 가능하나 회전은 항상 90도 방향이어야 하며 감시되는 방향은 수평 또는 수직이어야 합니다.

사무실의 크기와 상태, CCTV 정보 등을 고려하여 CCTV의 방향을 정확하게 판단하여 사각지대의 최소 크기를 결정하는 프로그램을 작성하시오.

해결

DFS+ 구현 문제입니다.
각 CCTV가 회전할 수 있는 횟수와 감시할 수 있는 방향만 설정하면 됩니다.
입력값의 범위가 1 ≤ N, M ≤ 8로 매우 작기 때문에 이를 Brute Force로 하는 것이 가능해 보인다.
각 CCTV의 회전 방향에 따라 달라지는 사각지대를 모두 찾아 그 중 최소값을 찾으면 된다.

구현 문제에 지문이 너무 좋았던 것 같아서 개인적으로 골드4 난이도는 아니었던 것 같습니다.
역시나 구현이 조금 까다로워서 불안하기도 했지만, 코드를 작성하기 전에 신중하게 설계해야 한다는 것을 다시 한 번 느꼈습니다.

import sys
from itertools import product
from copy import deepcopy

# 각각의 cctv 번호를 key로, 
# 회전에 따른 감시 가능한 방향의 경우의 수의 list를 value로 하는 딕셔너리로 정의
cctv = {
    1: (('right'), ('left'), ('up'), ('down')),
    2: (('right', 'left'), ('up', 'down')),
    3: (
        ('up', 'right'),
        ('right', 'down'),
        ('down', 'left'),
        ('left', 'up'))
    ,
    4: (('left', 'up', 'right'), ('up', 'right', 'down'), ('right', 'down', 'left'), ('down', 'left', 'up')),
    5: (('left', 'right', 'up', 'down'))
}


def dfs(x, y, key, v_idx):
    global N, M, d_arr
    # cctv 번호, 회전방향에 따라 감시할 수 있는 방향을 설정
    direction = cctv(key)(v_idx)
    # 감시할 수 있는 영역을 탐색
    for d in direction:
        if d == 'up':
            loc = x
            while loc - 1 >= 0:
                if d_arr(loc - 1)(y) == 6:
                    break
                if d_arr(loc - 1)(y) == 0:
                    d_arr(loc - 1)(y) = '#'
                loc -= 1
        elif d == 'right':
            loc = y
            while loc + 1 < M:
                if d_arr(x)(loc + 1) == 6:
                    break
                if d_arr(x)(loc + 1) == 0:
                    d_arr(x)(loc + 1) = '#'
                loc += 1
        elif d == 'left':
            loc = y
            while loc - 1 >= 0:
                if d_arr(x)(loc - 1) == 6:
                    break
                if d_arr(x)(loc - 1) == 0:
                    d_arr(x)(loc - 1) = '#'
                loc -= 1
        elif d == 'down':
            loc = x
            while loc + 1 < N:
                if d_arr(loc + 1)(y) == 6:
                    break
                if d_arr(loc + 1)(y) == 0:
                    d_arr(loc + 1)(y) = '#'
                loc += 1


def count_blind_spot():
    global N, M, d_arr
    result = 0
    for x in range(N):
        for y in range(M):
            if d_arr(x)(y) == 0:
                result += 1
    return result


N, M = map(int, sys.stdin.readline().split())
arr = ()
cctv_list = ()
for i in range(N):
    temp = list(map(int, sys.stdin.readline().split()))
    arr.append(temp)
    for j in range(M):
        if 1 <= temp(j) <= 5:
            cctv_list.append((i, j))
            
# cctv의 종류, 회전방향에 따라 발생할 수 있는 모든 경우의 수를 저장한 배열          
total_cctv_list = list(product(*((t for t in range(len(cctv(arr(i)(j))))) for i, j in cctv_list)))

answer = float('inf')
for data in total_cctv_list:
    d_arr = deepcopy(arr)
    # 감시영역을 갱신
    for i, cctv_dir in enumerate(data):
        loc_i, loc_j = cctv_list(i)
        cctv_key = arr(loc_i)(loc_j)
        dfs(loc_i, loc_j, cctv_key, cctv_dir)
    d_answer = count_blind_spot()
    # 사각지대(d_answer)의 최소 크기 갱신
    answer = min(d_answer, answer)
print(answer)