백준(boj) 15683_감시 (파이썬, c++)

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

풀이

---

감시하는 곳을 완전탐색 하면 된다. 이 때 비트마스크와 집합을 사용해서 좀 더 이쁘게 구현 가능하다.

우선 solve()함수부터 살펴보면, 이 함수는 완전탐색을 하기 위한 함수이다. pos로 현재 위치를 나타내고, res로 0인 곳을 얼마나 살폈는지를 나타낸다.(res를 사용하지 않고 base case 부분에 2중포문으로 a를 다 살펴보며 0이 몇개인가를 찾아도 되지만, 시간 절약을 위해 처음에 0의 개수를 세어놓고, 총 0의 개수에서 감시하는 cctv 개수를 빼줌으로써 남은 0의 개수를 구했다.)

pos가 모든 cctv를 살펴보면 끝이나게 base case를 잡고, b라는 지역변수에 a의 값을 복사해줬다.

그렇게 x좌표, y좌표, 몇번의 cctv인지를 저장해놓은 cctv_list를 살펴보며 그 번호의 cctv는 어느 방향들을 살펴볼 수 있는지 미리 만들어놓은 cctv 배열을 통해 확인한다.

search() 함수를 통해 res를 갱신해주는데, search()함수는 4방향을 살피면서 d가 속한 방향만 확인하게 된다. 예를 들어(파이썬 18line, c++ 23line) cctv[2]를 참조 하는 중이라서 d가 U|D라 하면, 4방향 중에 합집합 했을때 참이 되는 (1<<0), (1<<2)일 때 if문이 실행하게 된다. 즉 1, 4인 U와 D 방향으로 탐색을 하게 된다. 탐색 하면서 방문하는 a배열의 빈칸을 9로 만들어 줘서 방문한 0을 지워준다. 이 때 숫자도 하나씩 늘리면서 방문한 곳의 개수를 세어준다.

이렇게 모든 경우의 수를 살펴보며 남은 0의 개수(0의 총 개수 - 탐색한 cctv수)가 최소가 되는 값을 찾아주면 된다.

python3

from sys import*
input = stdin.readline
​
def solve(pos, res=0):
    global a
    ans=INF
    if pos == cctv_cnt: return zero_cnt - res     #base case
    b=[x[:] for x in a]
    x, y, c = cctv_list[pos]
    for d in cctv[c]:
        ans = min(ans, solve(pos+1, res+search(x, y, d)))
        a=[x[:] for x in b]
    return ans
​
def search(x, y, d):
    cnt=0
    for i in range(4):
        if d & (1<<i):
            dx, dy = dd[i]
            nx, ny = x, y
            while 1:
                nx += dx; ny += dy
                if(nx<0 or ny<0 or nx>n-1 or ny>m-1 or a[nx][ny]==6):break
                if a[nx][ny]==0:
                    cnt+=1
                    a[nx][ny]=9
    return cnt
​
INF = 1e9
U, R, D, L = 1, 2, 4, 8
cctv = [[0],
        [U, R, D, L],                                       #cctv 1
        [U|D, L|R],                                           #cctv 2
        [U|R, R|D, D|L, L|U],                       #cctv 3
        [U|R|D, R|D|L, D|L|U, L|U|R],       #cctv 4
        [U|R|D|L]]                                             #cctv 5
dd=[(-1,0), (0,1), (1,0), (0,-1)]
​
n,m=map(int,input().split())
cctv_list, a = [], []
cctv_cnt = 0
zero_cnt = 0
for i in range(n):
    a.append(list(map(int,input().split())))
    for j in range(m):
        if a[i][j]==0: zero_cnt += 1
        elif a[i][j]<6:
            cctv_cnt+=1
            cctv_list.append((i, j, a[i][j]))
print(solve(0, 0))

C++

#include<cstdio>
#include<vector>
#include<tuple>
#include<algorithm>
#include<memory.h>                 //memcpy 이거 아니면 cstring에 들어있음 
using namespace std;
typedef tuple<int, int, int> T;
const int INF = 1e9;
const int U = 1, R = 2, D = 4, L = 8;
vector<int> cctv[6] = {{},
                       {U, R, D, L},
                       {U|D, L|R},
                       {U|R, R|D, D|L, L|U},
                       {U|R|D, R|D|L, D|L|U, L|U|R},
                       {U|R|D|L}};
int dd[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
int n, m, a[8][8], cctv_cnt=0, zero_cnt=0; 
vector<T> cctv_list;
​
int search(int x, int y, int d){
    int cnt = 0;
    for(int i=0; i<4; i++){
        if(d & (1<<i)){
            int dx = dd[i][0], dy = dd[i][1];
            int nx = x, ny = y;
            while(1){
                nx += dx, ny += dy;
                if(nx<0 || ny<0 || nx>n-1 || ny>m-1 || a[nx][ny]==6)break;
                if(a[nx][ny]==0){
                    cnt++;
                    a[nx][ny]=9;
                }
            }
        }
    }
    return cnt;
}
​
int solve(int pos, int res){
    int ans = INF;
    int b[8][8];                //이거 전역변수로 선언해서 한참 헤맴 
    if(pos == cctv_cnt) return zero_cnt - res;
    memcpy(b, a, sizeof(a));
    int x, y, c;
    tie(x, y, c) = cctv_list[pos];
    for(int d: cctv[c]){
        ans = min(ans, solve(pos+1, res+search(x, y, d)));
        memcpy(a, b, sizeof(b));
    }
    return ans;
}
​
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &a[i][j]);
            if(a[i][j]==0) zero_cnt++;
            else if(a[i][j]<6){
                cctv_cnt++;
                cctv_list.push_back(make_tuple(i, j, a[i][j]));
            }
        }
    }
    printf("%d", solve(0, 0));
    return 0;
}

고찰

---

c++ 지역변수로 설정해야하는 b배열을 전역변수로 설정했다가 헤맸었음.