[알고리즘] - 조합

문제

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

15683번: 감시

 

풀이 팁

1. 문제를 보자마자 모든 경우의 수 ( cctv 마다 각자 회전하여 나오는 영역의  수 )를 구하는 문제라는 걸 알고, 백트래킹과 조합을 생각했다

2. 백트래킹을 푸는데 나는 계속 어느 시점에 초기화를 해야하는지 몰랐다.. 아시는 분은 여기 답좀 남겨주세요,....

https://www.acmicpc.net/board/view/138803

글 읽기 - 어떻게 수정을 해야할까요

3. 결국 cctv개수가 8개 이하라는 말에 시간복잡도가 괜찮을거 같다고 판단해서 조합을 통해서 풀었다

4. 다른 사람들 보니까 copy쓰시던데 나는 초기화함수 만들어서 사용했다

 

코드

import sys
from itertools import product

n,m = map(int,input().split())
arr = [
    list(map(int,input().split()))
    for _ in range(n)
]

temp = [
    [0 for _ in range(m)]
    for _ in range(n)
]

# 동 남 서 북 ( 시계 방향 )
dxs,dys = [0,1,0,-1],[1,0,-1,0]

min_val = n * m
cctv = []

cctv_direction = [
    [],
    [[0],[1],[2],[3]],
    [[0,2],[1,3]],
    [[0,1],[1,2],[2,3],[3,0]],
    [[0,1,2],[1,2,3],[2,3,0],[3,0,1]],
    [[0,1,2,3]],
]

for i in range(n):
    for j in range(m):
        if arr[i][j] in [1,2,3,4,5]:
            cctv.append((i,j, arr[i][j]))

def in_range(x,y):
    return 0<=x<n and 0<=y<m

def init_temp():
    for i in range(n):
        for j in range(m):
            temp[i][j] = arr[i][j]

def getSize():
    size = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                size += 1
    return size

tmp = []
for _, _,val in cctv:
    tmp.append(cctv_direction[val]) 

for prod in list(product(*tmp)):
    init_temp()

    for i in range(len(cctv)):
        for d in prod[i]:
            x, y, _ = cctv[i][0], cctv[i][1], cctv[i][2]

            while True:
                nx,ny = x + dxs[d], y + dys[d]

                if not in_range(nx,ny):
                    break
                if temp[nx][ny] == 6:
                    break
                if temp[nx][ny] == 0:
                    temp[nx][ny] = -1

                x,y = nx,ny

    min_val = min(min_val, getSize())
print(min_val)