감시 [백준 15683번]

문제

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

15683번: 감시

 

내 풀이

 

문제를 딱 봤을 때 모든 경우의 수를 구해야 하기 때문에 dfs를 사용해야 할 것 같았다. 그래서 먼저 CCTV의 번호와 위치를 cctv 리스트에 저장하였다.

 

CCTV는 번호에 따라서 감시하는 방향과 방향의 수가 다르다. 그래서 각 CCTV가 감시할 수 있는 모든 방향을 딕셔너리에 저장하였다.

 

그래고 dfs를 사용하여 모든 경우의 수를 구해주었다.

여기서 중요한 것은 tmp이다.

재귀를 돌리기 전에 tmp에 현재 space의 상태를 저장한다. 그리고 watch 함수에서 tmp의 상태를 바꿔준다. 감시를 할 수 있다면 그곳을 7로 바꿔준다.

dfs 함수에서 리턴을 하고 나면, tmp는 원상복귀 시킨다.

 

import sys
import copy
input = sys.stdin.readline

N, M = map(int, input().strip().split())
space = [list(map(int, input().strip().split())) for _ in range(N)]
cctv = []
for i in range(N):
    for j in range(M):
        if 0 < space[i][j] < 6:
            cctv.append((space[i][j], i, j))

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # 동 남 서 북
dir = {
    1: [[0], [1], [2], [3]],
    2: [[0, 2], [1, 3]],
    3: [[3, 0], [0, 1], [1, 2], [2, 3]],
    4: [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
    5: [[0, 1, 2, 3]]
}

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
            elif tmp[nx][ny] == 0: tmp[nx][ny] = 7

ans = 1e9
def dfs(idx, space):
    global ans
    tmp = copy.deepcopy(space)
    if idx == len(cctv):
        cnt = 0
        for t in tmp:
            cnt += t.count(0)
        ans = min(ans, cnt)
        return
    num, x, y = cctv[idx]
    for d in dir[num]:
        watch(x, y, d, tmp)
        dfs(idx+1, tmp)
        tmp = copy.deepcopy(space)
dfs(0, space)
print(ans)

 

총평

삼성 문제 너란 문제... 아직 나에게 왜 이렇게 어렵니...