[백준 15683] 파이썬 - 감시

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

15683번: 감시

 

 

# 조건

• 사무실은 1x1 크기의 정사각형으로 나누어져 있는 N x M 크기의 직사각형으로 나타낼 수 있다.
• 총 K개의 CCTV가 있는데 5종류가 존재
  • 한 쪽 방향
  • 서로 반대방향인 두 방향 - 상하, 좌우
  • 서로 직각인 두 방향 - 좌상, 좌하, 우상, 우하
  • 세 방향 감시
  • 네 방향 검사
• 검사할 수 있는 방향에 있는 칸 전체를 감시 가능
• 벽은 통과하지 못한다.
• 지도에서 0은 빈 칸, 6은 벽, 1-5는 CCTV 번호
• CCTV는 서로를 통과가능
• 사각지대의 최소 크기를 구하여라

 

# 접근 방법

• CCTV의 방향을 돌리며 DFS를 이용해주면 될 것 같다.
• 방 cctv마다 탐색할 수 있는 방향을 델타함수의 로 저장해준다.
• cctv의 좌표와 번호를 기록해준 후 cctv인덱스와 계속 바뀌는 방 카피본을 인자로 넣어주며 dfs 함수 시작
• 탈출 조건 -> 모든 cctv를 다 돌았다면 사각지대 카운트 해준 후 탈출
• cctv 언팩킹해주며 cctv종류에 따른 방향설정해준다.
• 중요한 점 하나는 현재 가질수 있는 방향마다 방을 deepcopy 해주어야 나중에 다른 cctv의 다른 방향을 검색할 때도 사용이 가능하다.
• 즉 1번 cctv의 첫번 째 방향 -> 2->마지막 번째 cctv의 1방향체크 후 돌아갔을 때 그 전까지 감시 기록이 남아 있어야 된다.

import sys, copy  
sys.stdin = open('input.txt')  

def dfs(n,room2):  
    global result  
    # cctv를 다 돌았다면  
    if n == len(cctv):  
        cnt = 0  
        # 사각지대 체크  
        for i in range(N):  
            cnt += room2[i].count(0)  
        result = min(result, cnt)  
        return  
    # cctv 위치, 종류 언패킹  
    x, y, kind_cctv = cctv[n]  
    # cctv 종류에 따라 방향 바꿔주면서 감시  
    for i in direct[kind_cctv]:  
        # 방향마다 감시구역을 초기화시켜주야한다.  
        # 초기화 시켜줄 방 카피        
        arr = copy.deepcopy(room2)  
        for k in i:  
            ni = x+di[k]  
            nj = y+dj[k]  
            # 범위 내에 있을 떄만  
            while 0<=ni<N and 0<=nj<M:  
                if arr[ni][nj] == 6:  
                    break  
                elif arr[ni][nj] == 0:  
                    arr[ni][nj] = 7  
                ni += di[k]  
                nj += dj[k]  
        dfs(n+1, arr)  

# 세로와 가로  
N, M = map(int, input().split())  
# 전체 좌표  
room = [list(map(int, input().split())) for i in range(N)]  

# cctv 좌표 따기  
cctv = []  
for i in range(N):  
    for j in range(M):  
        if 0 < room[i][j] < 6:  
            # 가로, 세로, cctv 번호 저장  
            cctv.append((i, j, room[i][j]))  

# cctv마다 탐색가능한 방향 - 값 = 델타함수 인덱스  
# direct의 인덱스 = cctv 번호  
direct = [  
    [],  
    [[0], [1], [2], [3]],  
    [[0, 2], [1, 3]],  
    [[0, 1], [1, 2], [2, 3], [0, 3]],  
    [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],  
    [[0, 1, 2, 3]]  
]  


# 상우하좌  
di, dj = [-1,0,1,0],[0,1,0,-1]  
# 결과값 저장  
result = 10000000  
dfs(0, room)  

print(result)