[Python/파이썬] 백준 15683번 감시

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

코드

answer = 64

n, m = map(int, input().split())
office = []
cctv = []
blank = 0
for i in range(n):
    line = list(map(int, input().split()))
    for j in range(m):
        if line[j] != 0 and line[j] != 6:
            cctv.append([i, j, line[j]])
        elif line[j] == 0:
            blank += 1
    office.append(line)

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

# cctv 종류에 따라서 이동 가능한 경우의 수
dir = {
    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]]
}


def move(x, y, dir_list):   # dir_list에 있는 모든 방향으로 최대한 이동
    visited = []
    for d in dir_list:
        nx = x
        ny = y
        while True:
            nx += dx[d]
            ny += dy[d]
            if nx < 0 or nx >= n or ny < 0 or ny >= m or office[nx][ny] == 6:
                break
            if office[nx][ny] == 0:
                visited.append((nx, ny))
                office[nx][ny] = 9
    return visited


def undo_move(visited):  # 이동하며 표시했던 것을 원래대로 되돌리기
    for x, y in visited:
        office[x][y] = 0


def dfs(idx, blank):
    global answer
    if idx == len(cctv):    # 모든 cctv를 다 시뮬레이션해봤을 때
        answer = min(answer, blank)
        return
    for dir_list in dir[cctv[idx][2]]:
        visited = move(cctv[idx][0], cctv[idx][1], dir_list)
        dfs(idx+1, blank-len(visited))
        undo_move(visited)


dfs(0, blank)
print(answer)

 

주어진 조건의 범위가 작은 경우에는 브루트포스로 모든 경우의 수를 다 해봐야하는 경우가 많은데, 이 문제가 딱 그런 케이스였던 것 같다.

 

코드는 길지만 풀이는 간단하다. 각 CCTV에서 모든 경우의 수를 다해보면 된다.

CCTV 종류 별로 가능한 이동을 미리 dir이라는 딕셔너리에 모두 저장해뒀다.

dir = {
    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를 순회하며 가능한 모든 조합을 실행해본 뒤 그 중 가장 사각지대가 적게 나오는 경우의 수를 구하면 된다.

 

시간 초과 걱정?

CCTV의 개수가 최대 8개이고, 각 CCTV에서 해볼 수 있는 경우의 수가 최대 4가지이므로 DFS는 최대 4^8 = 2^16번 실행되게 되므로 해볼만 한 계산 횟수이다.