[백준] 15683 - 감시

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

15683번: 감시

백준 문제집 중 '삼성 sw 역량 테스트 기출문제'에 포함된 문제

 

해당 문제집은 거의 대부분 Brute-Force 문제인 듯.

재귀를 이용하여 모든 경우를 계산하였다.

pypy2로 컴파일 했음에도 제한시간이 아슬아슬했다. 더 좋은 방법이 있을 듯

 

<Python 코드>

import sys
import copy
 
lines = sys.stdin.readlines()
n, m = tuple(map(int, lines[0].split()))
room = [list(map(int, line.split())) for line in lines[1:]]
cctv_list = []
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1] # 상, 우, 하, 좌
 
def recu(depth, sight_list):
    if depth == len(cctv_list):
        tmp_room = copy.deepcopy(room)
        for sight in sight_list:
            d, y, x = sight
            while(True):
                if y < 0 or y >= n or x < 0 or x >= m or room[y][x] == 6:
                    break
                tmp_room[y][x] = '#'
                y, x = y + dy[d], x + dx[d]
        re = 0
        for l in tmp_room:
            for p in l:
                if p == 0:
                    re += 1
        return re
    
    cctv = cctv_list[depth]
    case = []
    if cctv[0] == 1:
        for d in range(4):
            case.append([(d, cctv[1], cctv[2])])
    elif cctv[0] == 2:
        for d in range(2):
            case.append([(d, cctv[1], cctv[2]), (d+2, cctv[1], cctv[2])])
    elif cctv[0] == 3:
        for d in range(4):
            case.append([(d, cctv[1], cctv[2]), ((d+1)%4, cctv[1], cctv[2])])
    elif cctv[0] == 4:
        for d in range(4):
            case.append([(d, cctv[1], cctv[2]), ((d+1)%4, cctv[1], cctv[2]), ((d+2)%4, cctv[1], cctv[2])])
    elif cctv[0] == 5:
        case.append([(0, cctv[1], cctv[2]), (1, cctv[1], cctv[2]), (2, cctv[1], cctv[2]), (3, cctv[1], cctv[2])])
    re = 100
    for c in case:
        re = min(re, recu(depth+1, sight_list + c))
    return re
 
for i in range(n):
    for j in range(m):
        if 1<=room[i][j]<=5:
            cctv_list.append((room[i][j], i, j))
sys.stdout.write(str(recu(0, [])))