문제
풀이
이 문제는 주어진 입력의 갯수도 8개로 상당히 작고 cctv를 돌려서 얻을 수 있는 가능한 모든 상황을 고려해야하는 문제이므로 백트래킹으로 풀 수 있다.
cctv를 어떻게 효율적으로 잘 돌릴 것인가, 재귀함수의 로직을 어떻게 짤 것인가 이 두가지만 잘 고려하면 풀 수 있는 문제라고 생각한다. 물론 이게 무지막지하게 어렵다고 느껴지지만
우선 로직의 순서는 cctv의 갯수를 기준으로 경우의 수를 체크할 것이기 때문에(또한 매번 N*M 순회를 하는 것은 비효율적이므로) 따로 cctvs 라는 리스트에 추출해준다.
다 추출하고 나면 이제 count_blind_spot이라는 함수를 통해서 사각지대를 세어줄건데
그 전에 정해진 방향으로 blind_spot을 #으로 그려주는 paint_blind_spot함수를 통해 넘겨받은 direction이라는 weight값을 벽에 닿거나 리스트 바깥으로 벗어나기 전까지 더해주면서 0으로 되어있는 빈 값을 #으로 채워준다.
그렇게 경우의 수를 하나하나 스택에 쌓아주고 cctvs 리스트의 길이 만큼 depth가 깊어지면 한 사이클을 모두 돌았다는 의미기 때문에 0의 값의 갯수를 구해서 최소값 검사를 통해 업데이트를 해준다.
마지막으로 이 로직의 핵심은 copy.deepcopy를 통해 함수를 빠져나오면 coppied_cctv_map을 이전 값으로 돌려주는 것이라고 생각한다. for문 위에서 한 번 함수를 빠져나와서 한 번 선언해주면서 마치 백트래킹에서 visited나 is_used리스트를 선언해서 값을 넣어주고 함수가 끝나면 pop해주는 것처럼 사용했다.
from typing import List
import copy
import sys
def paint_blind_spot(row: int, col: int, direction:List[int], cctv_map:List[List[int]]) -> None:
for d in direction:
nrow, ncol = row, col
while 0 <= nrow < N and 0 <= ncol < M and cctv_map[nrow][ncol] != 6:
if cctv_map[nrow][ncol] == 0:
cctv_map[nrow][ncol] = "#"
nrow += directions[d][0]
ncol += directions[d][1]
def count_blind_spot(depth: int, cctv_map: List[List[int]]) -> None:
global answer
if depth == len(cctvs):
answer = min(answer , sum(map(lambda x: x.count(0), cctv_map)))
return
coppied_cctv_map = copy.deepcopy(cctv_map)
row, col, cctv_type = cctvs[depth]
for cctv_dir in cctv_direction[cctv_type]:
paint_blind_spot(row, col, cctv_dir, coppied_cctv_map)
count_blind_spot(depth+1, coppied_cctv_map)
coppied_cctv_map = copy.deepcopy(cctv_map)
if __name__ == '__main__':
sys.stdin = open('', 'r')
N, M = map(int, input().split())
cctv_map = [list(map(int, input().split())) for _ in range(N)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cctv_direction = [
[],
[[0], [1], [2], [3]],
[[0, 1], [2, 3]],
[[0, 2], [0, 3], [1, 2], [1, 3]],
[[0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3]],
[[0, 1, 2, 3]]
]
answer = int(10e9)
cctvs = []
for row_idx in range(N):
for col_idx in range(M):
if cctv_map[row_idx][col_idx] == 6:
continue
if cctv_map[row_idx][col_idx] != 0:
cctvs.append((row_idx,col_idx, cctv_map[row_idx][col_idx]))
count_blind_spot(0, cctv_map)
print(answer)
피드백
바킹독님이 몇시간이 걸리든 한 번 풀어보라고 해서 오늘 4시간 정도 들여서 겨우 풀 수 있었다. 사실 deepcopy를 활용한 부분은 디버그 모드로 이래저래 끼워맞추다 우연히 얻은 결과니 사실상 풀었다고 보기 어렵다.
그리고 direction 부분은 다른 분의 코드를 참고 했는데 나는 저렇게 줄일 방법이 떠오르지 않아서 일일히 방향을 다 쳤는데 저 코드를 보면서 무릎을 탁 쳤다.
그래도 어제 h님의 조언대로 타입을 명시해 더 코드를 보기 쉽게 만들었다. 또한 최대한 명시적인 변수명을 선언하려고 노력했다.
요즘 문제 푸는게 좀 즐거워지기 시작했다. 머리는 좀 아프지만 점점 느는 것 같아서 기쁘다.
