감시, python

문제 설명

cctv의 종류와 해당 cctv가 감시하는 방향이 주어졌을 때 감시받지 않는 사각지대의 최소 수를 구하는 문제다.

문제가 복잡하니 백준으로 가서 찬찬히 살펴본 다음에 해설을 보는 것을 추천한다.

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

15683번: 감시

문제 풀이

첫 번째 접근

문제에서 요구한 대로 입력을 받아줬다면, cctv가 갈 수 있는 방향을 먼저 배열로 정해줘야 한다.

이러한 문제에서 지금까지 그래왔듯이 북동남서의 방향대로 열과 행을 나눠서 저장한 다음, cctv의 숫자에 따라서 감시하는 방향을 설정해줘야 한다.

 

첫 번째 cctv를 예로 들어 보자. 간단하게 one이라고 표시하겠다. one의 경우에는 북동남서 각각 한 방향씩 감시하는 cctv이다. 그러므로 [0], [1], [2], [3]을 2차원 배열의 인덱스가 1인 배열에 넣어서 각 인덱스가 가지는 방향대로 움직이도록 한다. 그러니까 [0]의 경우에는 (-1, 0)으로 북쪽으로만 움직이고 [1]의 경우에는 (0, 1)로 동쪽으로만 움직이며 [2]의 경우에는 (1, 0)으로 남쪽으로만 움직인다. 마지막으로  [3]의 경우에는 (0, -1)로 서쪽으로만 움직인다.

 

두 번째 cctv인 경우는 어떻게 할까. two는 남북, 동서 이렇게 움직이도록 되어 있다. 그러므로 우리가 처음에 저장해줬던 북동남서 방향을 이용한다면, [0, 2]와 [1, 3]이 될 것이다. 왜냐하면 남북의 경우에는 dR과 dC의 인덱스 0과 2를 이용해서 움직이며 동서의 경우 dR과 dC의 인덱스 1과 3을 이용해서 움직이는 것이다.

 

위의 경우대로 다섯번째 cctv까지 넣어줬다면 기본 셋팅은 어느정도 끝난 것이다.

 

그 다음에는 지도에 있는 cctv의 종류와 위치를 cctves라는 배열에다가 저장을 한다. 또한 정답을 넣어줄 변수 answer에도 int(1e9)를 넣어 최댓값을 설정해준다.

 

두 번째로는 깊이 우선 탐색을 이용해서 감시 카메라가 감시할 수 있는 모든 경우의 수를 구해주는 것이다. 만일 count가 cctves의 길이와 같아 모든 감시 카메라를 돌았다면 사각지대의 수를 구한 다음 최솟 값을 구하고 return을 한다.

 

그렇지 않다면  cctves에서 count 위치에 있는 감시 카메라를 가지고 온다. 그리고 해당 감시 카메라가 갈 수 있는 위치를 하나씩 확인해준다. 여기서 중요한 점은 감시 카메라가 갈 수 있는 위치를 넣어준 다음에 원래대로 돌려주는 것이다. 그러므로 tmp 변수에다가 copy.deepcopy()를 이용해서 임시로 값을 넣어줘야 한다.

 

해당 위치로 감시 카메라가 감시할 수 있는 곳을 전부 표현했다면 다음 감시 카메라로 넘어가도록 한다. 그리고 하나의 함수 루틴이 끝나서 return이 되면 graph2에 다시 과거의 값을 넣어주면 된다.

 

코드

import sys
import copy
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split(" "))
graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split(" "))))

dR = [-1, 0, 1, 0] #북동남서
dC = [0, 1, 0, -1]
# 감시하는 방향
dWatch = [
    [],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [0, 3]],
    [[0, 1, 3], [0, 1, 2], [1, 2, 3], [0, 2, 3]],
    [[0, 1, 2, 3]]
]
# 감시 카메라의 종류와 위치를 넣는 배열
cctves = []
# 정답을 넣는 변수
answer = int(1e9)

# 리스트에 감시 카메라의 종류와 위치를 넣어준다.
for i in range(n):
    for j in range(m):
        if 1 <= graph[i][j] <= 5:
            # 감시 카메라의 종류, 열, 행
            cctves.append((graph[i][j], i, j))


# 주어진 그래프와 감시 카메라의 감시 위치를 가지고 감시할 수 있는 곳을 표시한다.
def make(graph3, arr, r, c):
    q = deque()

    # 감시 할 수 있는 곳을 -1로 표시한다.
    for a in arr:
        q.append((r, c))
        while q:
            cR, cC = q.popleft()

            nR = cR + dR[a]
            nC = cC + dC[a]

            if 0<= nR <n and 0<= nC <m:
                if graph3[nR][nC] != 6:
                    graph3[nR][nC] = -1
                    q.append((nR, nC))

    return graph3


# 깊이 우선 탐색으로 모든 감시 카메라의 경우의 수를 구해준다.
def dfs(count, graph2):
    # 모든 cctv를 확인했다면 사각지대가 어디 있는지 찾는다.
    if count == len(cctves):
        safe = 0
        global answer
        # 사각지대의 갯수를 세는 반복문
        for i in range(n):
            for j in range(m):
                if graph2[i][j] == 0:
                    safe += 1

        # 더 작은 걸 정답으로 한다.
        answer = min(answer, safe)
        return

    # 현재 위치에 있는 cctv 정보를 가지고 온다.
    num, r, c = cctves[count]

    # 현재 cctv가 갈 수 있는 곳을 방문한다.
    for cctv in dWatch[num]:
        tmp = copy.deepcopy(graph2)
        # 현재 cctv가 갈 수 있는 곳을 방문한 다음 해당 그래프를 이용해 다음 cctv로 넘어간다.
        dfs(count+1, make(graph2, cctv, r, c))
        # 새로운 cctv 경로를 넣어주기 위해 예전 값을 돌려준다.
        graph2 = copy.deepcopy(tmp)


dfs(0, graph)
print(answer)