[백준/Python] 감시

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

15683번: 감시

import copy

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
direction = {
    1: [[0], [1], [2], [3]],
    2: [[0, 2], [1, 3]],
    3: [[0, 1], [1, 2], [2, 3], [3, 0]],
    4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
    5: [[0, 1, 2, 3]]
} # cctv 종류에 따른 감시 방향

def watch(x, y, direction, tmp):
    for d in direction:
        nx, ny = x, y
        # 이동할 수 없을 때까지 이동하면서 '#'으로 변경
        while True:
            nx += dx[d]
            ny += dy[d]
            if nx < 0 or nx >= N or ny < 0 or ny >= M or tmp[nx][ny] == 6: # 이동 가능한 범위를 벗어나거나 벽이면 break
                break
            elif tmp[nx][ny] == 0: # 빈칸이면 감시 구역으로 변경
                tmp[nx][ny] = '#'

def dfs(n, graph):
    global ans
    tmp = copy.deepcopy(graph)
    
    if n == len(cctv):
        count = 0 # 빈칸 개수
        for t in tmp:
            count += t.count(0)
        ans = min(ans, count) # 사각지대 최소 크기를 구한다
        return

    x, y, c = cctv[n]
    # 해당 cctv의 종류에 따른 감시 구역을 구한다
    for d in direction[c]:
        watch(x, y, d, tmp)
        dfs(n+1, tmp)
        tmp = copy.deepcopy(graph)

cctv = [] # cctv 리스트
ans = 1e9 # 사각지대 크기

# cctv 찾기
for i in range(N):
    for j in range(M):
        if graph[i][j] != 0 and graph[i][j] != 6:
            cctv.append([i, j, graph[i][j]]) # x위치, y위치, cctv 종류

dfs(0, graph)
print(ans)

1. 필요한 정보를 입력받고 방향벡터(dx, dy)와 cctv 종류에 따른 감시 방향 리스트(direction)를 생성한다.

2. 입력받은 사무실 정보(graph)에서 cctv만 찾아 리스트에 저장한다.

3. 모든 경우를 탐색한다.

    3-1. 현재 탐색하고 있는 cctv 정보를 가져와 해당 cctv의 종류에 따른 감시 구역을 구한다.

    3-2. 이동할 수 없을 때까지 이동하면서 '#'으로 변경한다.

    3-3. 변경이 끝났다면 다음 cctv로 넘어가 위의 과정을 반복한다.

    3-4. 모든 cctv의 탐색이 끝났다면 사각지대의 최소 크기를 구한다.

4. 결과를 출력한다.