[백준] 15683번: 감시 (골드4, 파이썬)

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

15683번: 감시

 

아이디어

1시간동안 bfs + dp 로 풀려고 노력했는데... dfs로 푸는 문제(브루트포스?)였다. 

 

1. 입력받은 maps의 원소를 순회하며 카메라가 있으면 cctv 리스트에 추가한다. (x, y, 카메라 종류)
2. 현재 깊이(depth)와 맵 정보(m)를 받는다.
3. 만약 depth가 cctv 리스트의 길이와 같으면
   
   1. 현재 맵(m)에 있는 사각지대(0)의 수를 센다.
   2. min_value(사각지대 최솟값)보다 구한 count가 더 작으면 값을 업데이트 해준다.
   3. return
4. 같지 않으면
   1. tmp_maps를 만들어 현재 맵(m)을 깊은 복사 해준다.
   2. 미리 만든 cctv의 시야 경우의 수를 담은 cctv_directions에서 해당 cctv가 볼 수 있는 방향의 정보를 모두 받아온다.
   3. 방향 정보를 0부터 끝까지 순회한다.
      1. 순회하면서 현재 방향에 따라 현재 맵에서 감시되는 부분은 0에서 -1로 변경해준다. (맵 업데이트)
      2. dfs(현재 depth + 1, 현재 맵 정보)를 호출한다. (2번부터 반복)
      3. 보드 초기 상태로 초기화해준다.

 

cctv_directions

# 북동남서
dv = [(-1, 0), (0,1), (1, 0), (0, -1)]

cctv_directions = {1: [[0], [1], [2], [3]],
                   2: [[1, 3], [0, 2]],
                   3: [[0, 1], [1, 2], [2, 3], [3, 0]],
                   4: [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
                   5: [[0, 1, 2, 3]]}

dv는 각각 북쪽, 동쪽, 남쪽, 서쪽으로 이동할 때의 방향 벡터이다. 이를 먼저 정의하고 각 cctv로 감시할 수 있는 방향의 경우를 모두 넣어주었다.

 

코드

import copy


       
N, M = map(int, input().split())
maps = [[int(x) for x in input().split()] for _ in range(N)]

# 북동남서
dv = [(-1, 0), (0,1), (1, 0), (0, -1)]

cctv_directions = {1: [[0], [1], [2], [3]],
                   2: [[1, 3], [0, 2]],
                   3: [[0, 1], [1, 2], [2, 3], [3, 0]],
                   4: [[0, 1, 2], [0, 1, 3], [1, 2, 3], [0, 2, 3]],
                   5: [[0, 1, 2, 3]]}

min_value = 1e9

cctv = []            
for i in range(N):
    for j in range(M):
        if 0 < maps[i][j] < 6:  # 카메라가 있으면
            cctv.append((i, j, maps[i][j])) # x, y, 카메라 정보

def find_sight(m, directions, x, y):
    for d in directions:
        nx = x
        ny = y
        while True:
            nx += dv[d][0]
            ny += dv[d][1]

            if nx < 0 or nx >= N or ny < 0 or ny >= M or m[nx][ny] == 6:
                break
            elif m[nx][ny] == 0:
                m[nx][ny] = -1


def dfs(depth, m):
    global min_value
    if depth == len(cctv):
        count = 0
        for mm in m:  # 0 개수 세기(사각지대 수)
            count += mm.count(0)
        min_value = min(min_value, count)
        return
    
    tmp_maps = copy.deepcopy(m)
    x, y, n = cctv[depth]

    for directions in cctv_directions[n]:
        find_sight(tmp_maps, directions, x, y)
        dfs(depth+1, tmp_maps)
        tmp_maps = copy.deepcopy(m) # 보드 초기화

dfs(0, maps)
print(min_value)