BOJ 15683: 감시 작성일 2020-02-13 https://www.acmicpc.net/problem/15683 2월동안 187문제 풀기(지난달 누적 87개) (18/187) 빠르고 침착하게 완전탐색 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include <bits/stdc++.h> using namespace std; int N, M, cnt, ans = 100; struct Point { int x, y, type; }; vector<vector<int>> arr; vector<Point> cctv; void input() { cin >> N >> M; arr.resize(N, vector<int>(M)); for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { cin >> arr[i][j]; if(arr[i][j] == 0) cnt++; else if(arr[i][j] < 6) cctv.push_back({i,j,arr[i][j]}); } } } const int dx[4] = {-1,0,1,0}; const int dy[4] = {0,1,0,-1}; bool bound(int x, int y) { return x >= 0 && x < N && y >= 0 && y < M; } void fill(int x, int y, int d) { while(1) { int nx = x + dx[d]; int ny = y + dy[d]; if (!bound(nx,ny)) break; if(arr[nx][ny] == 6) return; if(arr[nx][ny] == 0) arr[nx][ny] = 7, cnt--; x = nx, y = ny; } } void go(int cc) { if(cc == cctv.size()) { ans = min(ans, cnt); return; } auto bak = arr; int bakCnt = cnt; Point cur = cctv[cc]; for(int d = 0; d < 4; d++) { fill(cur.x, cur.y, (d+0)%4); if(cur.type == 2 || cur.type == 4 || cur.type == 5) fill(cur.x, cur.y, (d+2)%4); if(cur.type == 3 || cur.type == 4 || cur.type == 5) fill(cur.x, cur.y, (d+1)%4); if(cur.type == 5) fill(cur.x, cur.y, (d+3)%4); go(cc+1); arr = bak; cnt = bakCnt; } } int main() { input(); go(0); cout << ans; }