[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 15683번 _ 감시

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

15683번: 감시

[문제]

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

 

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.

[출력]

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

[아이디어]

1) cctv 2번은 2가지, 5번은 1가지, 나머지는 4가지 중 하나의 위치를 잡아야한다.

2) 각 cctv의 위치를 배열에 저장하면서, cctv 번호와 해당 cctv들이 가질 수 있는 위치 정보들을 배열에 담는다.

3) cctv가 가질 수 있는 위치 정보의 배열로 만들 수 있는 모든 조합을 찾는다.(product 이용)

4) 각 경우들에 대하여 (m*n - cctv의 수 - 벽의 수 - 감시하는 공간의 수)를 계산해 사각지대의 수의 최소를 찾는다.

(감시하는 공간의 수가 가장 많을 때가 최소이다.)

 

from itertools import product as p
n,m= map(int,input().split())
g = [list(map(int,input().split())) for _ in range(n)]

def cctv(cctvs,n,m,directions,g):
    dx = (-1,0,1,0); dy= (0,1,0,-1)
    d = {1:[[0],[1],[2],[3]],2:[[1,3],[0,2]],3:[[0,1],[1,2],[2,3],[3,0]],4:[[0,1,3],[0,1,2],[1,2,3],[0,2,3]],
        5:[[0,1,2,3]]}
    cnt= set()
    tmp = []
    for (i,j,num), direcs in zip(cctvs,directions):
        x,y = i,j
        if 1<=num<=5:
            direc = d[num][direcs]
            for k in direc:
                i,j = x,y
                while True:
                    if not (0<=i+dx[k]<n and 0<=j+dy[k]<m): break
                    else:
                        i += dx[k]; j += dy[k]
                        if g[i][j]==6: break
                        elif g[i][j]==0:
                            cnt.add((i,j))
    return len(cnt)  
                
cctvs = []
cnt2 = 0
directions = []
for i in range(n):
    for j in range(m):
        if 1<=(t:=g[i][j])<=5:
            cnt2+=1
            cctvs.append((i,j,t))
            if t == 2:
                directions.append([0,1])
            elif t==5:
                directions.append([0])
            else:
                directions.append([0,1,2,3])
        elif t ==6:
            cnt2+=1
directions = list(p(*directions))           

print(n*m - max([cctv(cctvs,n,m,direction,g) for direction in directions]) - cnt2)