15863 - 감시

 

---

 

문제

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

15683번: 감시

 

풀이

완탐 + 구현문제이다.

 

첫번째로 cctv 종류와 cctv위치를 배열에 저장한다.

 

다음으로 cctv별로 회전할 수 있는 경우의 수를 모두 구한다. 나는 일관성을 가지기 위하여 모두 4방향으로 회전한다고 가정했으며 [ 0, 1, 2, 3 => 우, 하, 좌, 상 ] 순으로 정의했다. 이 때 itertools product를 통하여 모든 경우의 수를 만들었다.

 

마지막으로 3차원 배열을 정의한다. 코드상에서 cctv_d 배열이며,

cctv_d[cctv종류][방향] 값을 넣어주면 감시해야하는 방향이 들어있는 1차원 배열을 얻을 수 있다.

 

그리고 미리 정의해둔 탐색함수(search) 에 위치와 방향을 매개변수로 던져주고 감시 범위를 체크하면 된다.

 

코드

import copy
import itertools
from sys import stdin
import sys

def search(x, y, d):
    global dx, dy, n, m, temp

    while True:
        nx = x + dx[d]
        ny = y + dy[d]

        # 범위 안에 있으며 벽이 아니라면
        if 0 <= nx < n and 0 <= ny < m and temp[nx][ny] != 6:
            # 빈칸일경우 방문처리 해준다. cctv면 그냥 넘어가면 된다.
            if temp[nx][ny] == 0:
                temp[nx][ny] = 9
            x = nx
            y = ny
        else:
            break


# Initialize
n, m = map(int, input().split())
office = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
cctvs = []
answer = sys.maxsize
for i in range(n):
    for j in range(m):
        if office[i][j] != 0 and office[i][j] != 6:
            cctvs.append([office[i][j], [i, j]])

# cctv 회전의 모든 경우의 수
directions = itertools.product([0, 1, 2, 3], repeat=len(cctvs))

# 우 하 좌 상 순서
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


# cctv_d[cctv번호][경우의 수 방향]
cctv_d = [
    [[]],
    [[0], [1], [2], [3]],
    [[0, 2], [1, 3], [0, 2], [1, 3]],
    [[0, 1], [1, 2], [2, 3], [3, 0]],
    [[3, 0, 1], [0, 1, 2], [1, 2, 3], [2, 3, 0]],
    [[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]
]

# 특정 그래프를 탐색하려면, 좌표와 방향을 지시해주어야 한다.
for dire in directions:
    temp = copy.deepcopy(office)
    # 해당 사이즈는 cctv 크기와 같다.
    for j in range(len(dire)):
        # 각 cctv와 회전에 맞게 값을 넣어준다.
        for val in cctv_d[cctvs[j][0]][dire[j]]:
            x, y = cctvs[j][1]
            search(x, y, val)

    temp_ans = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                temp_ans += 1

    # for v in temp:
    #     print(v)
    # print()
    answer = min(answer, temp_ans)



print(answer)

 

후기

 

탐색부분에 있어 잘하면 최적화를 더 할 수 있을 거 같긴 하다, 중복되는 부분이 워낙 많다보니 말이다.

 

근데 그렇게 생각하니 더 머리 아파서, 무식하지만 브루트포스로 풀었다.. 제한범위가 워낙 작다보니 가능했던 거 같다.