[백준(파이썬/Python)] 15683_감시 - 구현, 시뮬레이션

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

15683번: 감시

 

 

이 문제에서 핵심적인 부분은 어떻게 모든 카메라의 관찰 방향의 조합을 다 찾아서 그 때의 감시를 받지 않는 구역의 개수를 체크할 것인가입니다.

 

저같은 경우에는 카메라마다 감시 방향도 깔끔하게 떨어지지가 않아서 카메라 1~5번 마다 cam{n}_direction이라는 방향을 입력해주었고, 감시 방향을 순회하기 위해 [[방향1의 방향들], [방향2의 방향들]...] 식으로 3차원 리스트를 생성했습니다.

 

이후에는 맨 처음에 기록한 카메라의 위치와 타입을 기반으로 타입별로 checkArea()함수를 통해 감시 구역을 체크했고, 각 방향에서의 감시 구역을 리스트로 담아두었습니다. 이렇게 하면 camera라는 변수에는 [x좌표, y좌표, 타입, 방향별 감시구역 리스트]가 담기게 되죠.

 

최종적으로는 모든 camera들을 반복하면서 combination을 통해 감시 구역들의 조합을 생성했고, set 자료구조를 통해 모든 카메라들이 감시하고 있는 구역을 더했습니다. 그리고 맨 처음 감시받지 않고 있던 구역에서 이 구역을 빼줌으로써 그 최소값을 구했습니다.

 

골드5라고 하기에는 상당히 까다롭게 느껴졌던 문제였던 것 같습니다(제가 어렵게 풀어서 그런거일수도...).

 

[풀이]

import sys
from collections import deque
from itertools import product

input = sys.stdin.readline


unwatched = 0
answer = 100000
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
camera = []
for i in range(n):
    for j in range(m):
        # 카메라의 위치와 어떤 종류의 카메라인지를 기록
        if 1 <= graph[i][j] <= 5:
            camera.append((i,j, graph[i][j], []))
        elif graph[i][j] == 0:
            unwatched += 1


# 각 감시카메라의 관찰 방향
cam1_direction = [[[-1,0]],[[1,0]],[[0,-1]],[[0,1]]]
cam2_direction = [[[-1,0],[1,0]],[[0,-1],[0,1]]]
cam3_direction = [[[-1,0],[0,-1]], [[-1,0],[0,1]], [[1,0],[0,-1]], [[1,0],[0,1]]]
cam4_direction = [[[-1,0],[1,0],[0,-1]], [[-1,0],[1,0],[0,1]], [[-1,0],[0,-1],[0,1]],[[1,0],[0,-1],[0,1]]]
cam5_direction = [[[-1,0],[1,0],[0,-1],[0,1]]]


def checkArea(camera_direction, cam):
    for direction in camera_direction:
        area = []
        for d in direction:
            q = deque()
            q.append((x,y))
            while q:
                ax, ay = q.popleft()
                nx, ny = ax + d[0], ay + d[1]
                if 0 <= nx < n and 0 <= ny < m:
                    if graph[nx][ny] == 6:
                        break
                    else:
                        q.append((nx,ny))
                        if graph[nx][ny] == 0:
                            area.append((nx,ny))
        cam[3].append(area)

# 각 카메라별로 감시할 수 있는 구간을 기록해본다
for cam in camera:
    x, y, type = cam[0], cam[1], cam[2]
    if type == 1:
        checkArea(cam1_direction, cam)
    elif type == 2:
        checkArea(cam2_direction, cam)
    
    elif type == 3:
        checkArea(cam3_direction, cam)
    
    elif type == 4:
        checkArea(cam4_direction, cam)
    
    elif type == 5:
        checkArea(cam5_direction, cam)

area_list = []
for cam in camera:  
    area_list.append(cam[3])

area_comb = list(product(*area_list))
for area in area_comb:
    checked = set()
    for a in area:
        for x, y in a:
            checked.add((x,y))
    if answer > unwatched - len(checked):
        answer = unwatched - len(checked)
print(answer)