[백준][파이썬] 15683번 감시

문제 번호 : 15683
문제 출처 : https://www.acmicpc.net/problem/15683

Code

import sys


def watch(watched_set, index):              # index : count, cctv 개수 만큼 탐색
    if index == len(cctvs):
        result.append(len(watched_set))
        return
    else:
        for cctv in cctvs[index]:           # cctv[index] 에는 한 cctv의 경우의 수가 모두 저장
            new_s = set(watched_set)
            view(cctv, new_s)               # 각도에 따라서 cctv로 볼 수 있는 위치를 집합에 저장
            watch(new_s, index + 1)


def view(cc, viewd):
    x, y, cctv_type, angle = cc
    d = []
    for idx in range(4):
        d = direction[cctv_type][(idx + angle) % 4] # cctv type과 angle이 정해졌을 때 방향
        if d == 1:
            nx, ny = x + dx[idx], y + dy[idx]
            while -1 < nx < h and -1 < ny < w and office[nx][ny] != 6:
                if office[nx][ny] == 0:     # cctv 있는 위치는 저장 안하도록
                    viewd.add((nx, ny))
                nx = nx + dx[idx]
                ny = ny + dy[idx]


h, w = map(int, input().split())
office = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

angles = [4, 2, 4, 4, 1]        # type별로 가능한 각도 수
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
direction = [[0, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1,], [1, 1, 1, 1]] # 각도 별로 shift할 리스트

cctvs = []
answer = 0
result = []

for i in range(h):
    for j in range(w):
        if 0< office[i][j] <6:  # cctvs 에 하나의 cctv에서 가능한 각도를 하나의 리스트에 모두 저장
            cctvs.append([[i, j, office[i][j] - 1, angle] for angle in range(angles[office[i][j] - 1])])
        if office[i][j] == 0:   # 0의 개수 세기기
            answer+= 1
watched = set([])

watch(watched, 0)
answer = answer - max(result)   # 0의 개수에서 cctv로 본 위치의 수 빼서 답 구하기
print(answer)

Idea

1. cctv 종류 별로 가능한 각도 수가 다르다.
2. 처음에는 cctv로 본 곳을 #으로 표시했는데 시간이 많이 걸렸다.
3. 입력받은 이차원 리스트를 수정하지 않고 cctv가 본 위치를 저장하는 집합을 만들었다.
4. cctv가 본 위치가 가장 많은 상황에서 0의 개수에서 집합의 길이를 빼면 사각지대를 구할 수 있다.