감시

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

15683번: 감시

문제요약:

2차원 배열이 주어지고 1번부터 5번은 카메라 6번은 벽을 의미한다, 각각 카메라는 볼수 있는 각도가 다르고 회전이 가능 할 때 가장 안전지대가 적을때를 구하여라

 

소요시간:

50분

난이도 골드4

 

코딩:

import sys
import math
import copy
input = sys.stdin.readline
sys.setrecursionlimit(10000) 

n,m = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(n)]

dy = [-1,0,1,0]
dx = [0,1,0,-1]

camera = []
cam_5 = []

#카메라의 위치 찾기
for y in range(n):
    for x in range(m):
        if 0<arr[y][x]<5:
            camera.append([y,x,arr[y][x]])
        if arr[y][x] == 5:
            cam_5.append([y,x])

#벽에 부딫히기 전까지 카메라가 볼수 있는것 표시
def go(temp,y,x,i):
    ny = y
    nx = x
    while True:
        ny += dy[i]
        nx += dx[i]
        if 0<=ny<n and 0<=nx<m and temp[ny][nx]!=6:
            if temp[ny][nx]==0:
                temp[ny][nx] = '#'
        else:
            return

#카메라에 따라 방향 전환
def check(temp,dir,y,x,cam):
    if cam == 5:
        for i in range(4):
            go(temp,y,x,i)
    else:
        go(temp,y,x,dir)     
        elif cam == 2:
            dir +=2
            if dir>=4:
                dir-=4
            go(temp,y,x,dir)
        elif cam ==3:
            dir +=1
            if dir>=4:
                dir-=4
            go(temp,y,x,dir)
        elif cam==4:
            dir +=1
            if dir>=4:
                dir-=4
            go(temp,y,x,dir)
            dir +=1
            if dir>=4:
                dir-=4
            go(temp,y,x,dir)

#5번카메라는 변하지 않으므로 , 미리가놓기
for y,x in cam_5:
    check(arr,-1,y,x,5)
ans = int(1e9)

def dfs(arr,num):
    global ans
    if num == len(camera):
        if (zero :=sum([i.count(0) for i in arr])) < ans:
            ans = zero
        return
        
    y,x,cam = camera[num]
    for dir in range(4):    
        temp = copy.deepcopy(arr)
        check(temp,dir,y,x,cam)
        dfs(temp,num+1)

dfs(arr,0)
print(ans)

전형적인 dfs, 구현 문제이며, 구조가 복잡하진 않지만 필요한것을 빠르게 구현하는것이 관건인것같습니다. 카메라들의 위치를 먼저 찾고 이때, 5번카메라는 회전에 따라 바뀌지 않기 때문에 , 따로 찾아 미리 표시해 주었습니다. 그리고 카메라들의 방향을 바꿔가며 dfs를 진행했고, 끝났을때 제일 작은 답을 찾아 기록했습니다.