[BOJ] 15683. 감시 (🥇 , 구현/시뮬레이션)

문제

각 cctv의 방향에 따라 감시 지역을 설정하고, 감시 되지 않는 사각지대의 최소값을 구하는 문제

풀이

백준 연구소 시리즈랑 좀 비슷하다고 느꼈다.

1. cctv의 번호와 위치를 구한다
2. 각 cctv를 돌면서 하나씩 방향에 따라 감시지역을 설정한다. 처음엔 북쪽 방향, 그 다음엔 남쪽 방향 등등...
3. 1번 cctv의 감시지역을 설정했다면 그 다음엔 재귀를 돌려서 2번 카메라의 cctv를 설정하는 등.. 이런식으로해서 마지막 cctv의 감시지역까지 처리했다면 최종적으로 몇 개의 지역이 처리됐는지 최댓값을 구하면 사각지대의 최소값을 구할 수 있음

코드

방문처리를 하는 v배열을 사용하는 게 시간이 오래 걸리는 것 같다. 최단 시간 코드들을 보면서 리팩토링해야 할 거 같다.

# 348ms

def cctv(c, n, t=1):
    cctvs, i = [], 0
    while i < n:
        tmp, j = [], 0
        while j < c:
            tmp.append(dirs[(i+j*t)%4])
            j += 1
        cctvs.append(tmp)
        i += 1

    return cctvs

# cctv들의 위치랑 번호 찾아서 배열로 반환
def cctv_wall():
    ctv, walls = [], 0
    for i in range(1, N+1):
        for j in range(1, M+1):
            if 0<arr[i][j]<6:
                ctv.append((arr[i][j], i, j))
            elif arr[i][j] == 6:
                walls += 1
    return ctv, walls, len(ctv)+walls

def sol(k, v, cnt):
    global max_cnt
    if k == len(ctvs):
        max_cnt = max(max_cnt, cnt)
        return 
    
    num, i, j = ctvs[k]
    for dir in ctv_num[num]:
        c = 0
        tmp_v = [row[:] for row in v]
        for di, dj in dir:
            si, sj = i+di, j+dj
            while (a:=arr[si][sj])!=6:
                if a == 0 and v[si][sj] != '#':
                    c += 1
                    v[si][sj] = '#'
                si += di
                sj += dj
        sol(k+1, v, cnt+c)
        v = [row[:] for row in tmp_v]


N, M = map(int, input().split())
arr = [[6]*(M+2)] +[[6]+list(map(int, input().split()))+[6] for _ in range(N)]+[[6]*(M+2)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ctv_num = {
    1: cctv(1, 4), 
    2: cctv(2, 2, 2), 
    3: cctv(2, 4),
    4: cctv(3, 4), 
    5: cctv(4, 1)
}

visit = [[0]*(M+2) for _ in range(N+2)]
ctvs, walls, ctvwall = cctv_wall()
max_cnt = 0


sol(0, visit, 0)
print(N*M-ctvwall-max_cnt)

참고한 코드

백준에 있는 코드를 참고 했는데, 우선 cctv의 위치와 번호 정보를 얻을 때, 이미 그 하나의 cctv에서 얻을 수 있는 감시 지역의 정보를 전부 구한다. 그런 다음 그 위치 데이터들을 set()에 넣고 방문 처리 없이 재귀를 돌리면 최종적으로 구해진 set(감시 지역 정보)들을 가지고 사각지대의 개수를 구할 수 있는 것.

• cctv의 위치와 배열 값들은 변하지 않기 때문에 각 cctv마다 감시할 수 있는 구역들을 최초로 딱 한 번 구해두면 된다.

def watch(i, j, *cctv):
    global watch_spot
    spot_list = []
    for dir in cctv:
        spot = set()
        for d in dir:
            ni, nj = i+di[d], j+dj[d]
            while arr[ni][nj] != 6:
                if not arr[ni][nj]:
                    spot.add((ni, nj))
                ni += di[d]
                nj += dj[d]
        spot_list.append(spot)
    
    watch_spot[(i, j)] = spot_list

• cctv들이 감시할 수 있는 구역의 방향들에 대해서는 직접 입력해줬다. for문을 쓰는 것보다 덜 복잡

for i in range(1, N+1):
    for j in range(1, M+1):
        a = arr[i][j]
        if a == 0:
            zero_spot += 1
        elif a == 1:
            watch(i, j, [0], [1], [2], [3])
        elif a == 2:
            watch(i, j, [0, 2], [1, 3])
        elif a == 3:
            watch(i, j, [0, 1], [1, 2], [2, 3], [3, 0])
        elif a == 4:
            watch(i, j, [0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1])
        elif a == 5:
            watch(i, j, [0, 1, 2, 3])

리팩토링 후 코드

• 104ms

import sys
input = sys.stdin.readline

def watch(i, j, *cctv):
    global watch_spot
    spot_list = []
    for dir in cctv:
        spot = set()
        for d in dir:
            ni, nj = i+di[d], j+dj[d]
            while arr[ni][nj] != 6:
                if not arr[ni][nj]:
                    spot.add((ni, nj))
                ni += di[d]
                nj += dj[d]
        spot_list.append(spot)
    
    watch_spot[(i, j)] = spot_list
                
def sol(i, spots, K):
    global blind
    if i == K:
        blind = min(blind, zero_spot-len(spots))
        return 
    
    for watch_list in watch_spot[cctvs[i]]:
        sol(i+1, spots | watch_list, K)

N, M = map(int, input().split())
arr = [[6]*(M+2)] +[[6]+list(map(int, input().split()))+[6] for _ in range(N)]+[[6]*(M+2)]
di, dj = (-1, 0, 1, 0), (0, 1, 0, -1)

zero_spot, blind = 0, 1e13
watch_spot = dict()
for i in range(1, N+1):
    for j in range(1, M+1):
        a = arr[i][j]
        if a == 0:
            zero_spot += 1
        elif a == 1:
            watch(i, j, [0], [1], [2], [3])
        elif a == 2:
            watch(i, j, [0, 2], [1, 3])
        elif a == 3:
            watch(i, j, [0, 1], [1, 2], [2, 3], [3, 0])
        elif a == 4:
            watch(i, j, [0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1])
        elif a == 5:
            watch(i, j, [0, 1, 2, 3])

cctvs = list(watch_spot.keys())

sol(0, set(), len(cctvs))
print(blind)

후기

구현 문제를 풀다보니 문제가 원하는 요구 사항을 순서대로 정확하게 구현하는 것도 중요하지만 최초 한 번만 구하고 갖다 쓸 수 있는 부분들에 대해서는 고려를 해주는 게 시간을 훨씬 단축시킨다는 걸 알았당
처음 한 번 구해놓고 가져다쓰는게 매번 구하는 것보다 훨씬 빠를 것 같다면 그렇게도 생각해보는 연습을 해봐야할 거 같다.