[ 간신히 푼 코드 ]
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
int N,M,ans=1e9;
vector<pair<int,int>> v;
char origin[10][10];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int c1[4][2] = {{dx[3],dy[3]},{dx[2],dy[2]},{dx[1],dy[1]},{dx[0],dy[0]}};
int c2[2][4] = {{dx[2],dy[2],dx[3],dy[3]},{dx[0],dy[0],dx[1],dy[1]}};
int c3[4][4] = {{dx[0],dy[0],dx[3],dy[3]},{dx[0],dy[0],dx[2],dy[2]},
{dx[1],dy[1],dx[2],dy[2]},{dx[1],dy[1],dx[3],dy[3]}};
int c4[4][6] = {{dx[0],dy[0],dx[2],dy[2],dx[3],dy[3]}, {dx[0],dy[0],dx[1],dy[1],dx[2],dy[2]},
{dx[1],dy[1],dx[2],dy[2],dx[3],dy[3]}, {dx[0],dy[0],dx[1],dy[1],dx[3],dy[3]}};
int c5[8] = {dx[0],dy[0], dx[1],dy[1], dx[2],dy[2], dx[3],dy[3]};
void func(int depth, char board[10][10], int d1, int d2, int d3, int d4){
if(depth == v.size()){
int cnt=0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(board[i][j] == '0') cnt++;
ans = min(ans,cnt);
return;
}else{
int y = v[depth].first;
int x = v[depth].second;
char val = board[y][x];
char boardCP1[10][10];
char boardCP2[10][10];
char boardCP3[10][10];
for(int a=0;a<10;a++)
for(int b=0;b<10;b++)
{
boardCP1[a][b] = board[a][b];
boardCP2[a][b] = board[a][b];
boardCP3[a][b] = board[a][b];
}
if(val == '1'){
if(d1 == 0){
func(depth,boardCP1,1,0,0,0);
func(depth,boardCP2,2,0,0,0);
func(depth,boardCP3,3,0,0,0);
}
while(true)
{
int nx = x + c1[d1][0];
int ny = y + c1[d1][1];
if(nx<0 or ny<0 or nx>=M or ny>=N) break;;
if(board[ny][nx] == '6') break;
if(board[ny][nx] == '0')
board[ny][nx] = '#';
y = ny;
x = nx;
}
}else if(val == '2'){
if(d2 == 0){
func(depth,boardCP1,0,1,0,0);
}
for(int k=0;k<3;k+=2)
{
y = v[depth].first;
x = v[depth].second;
while(true)
{
int nx = x + c2[d2][k];
int ny = y + c2[d2][k+1];
if(nx<0 or ny<0 or nx>=M or ny>=N) break;
if(board[ny][nx] == '6') break;
if(board[ny][nx] == '0')
board[ny][nx] = '#';
y = ny;
x = nx;
}
}
}else if(val == '3'){
if(d3 == 0){
func(depth,boardCP1,0,0,1,0);
func(depth,boardCP2,0,0,2,0);
func(depth,boardCP3,0,0,3,0);
}
for(int k=0;k<3;k+=2)
{
y = v[depth].first;
x = v[depth].second;
while(true)
{
int nx = x + c3[d3][k];
int ny = y + c3[d3][k+1];
if(nx<0 or ny<0 or nx>=M or ny>=N) break;;
if(board[ny][nx] == '6') break;
if(board[ny][nx] == '0')
board[ny][nx] = '#';
y = ny;
x = nx;
}
}
}else if(val == '4'){
if(d4 == 0){
func(depth,boardCP1,0,0,0,1);
func(depth,boardCP2,0,0,0,2);
func(depth,boardCP3,0,0,0,3);
}
for(int k=0;k<5;k+=2)
{
y = v[depth].first;
x = v[depth].second;
while(true)
{
int nx = x + c4[d4][k];
int ny = y + c4[d4][k+1];
if(nx<0 or ny<0 or nx>=M or ny>=N) break;;
if(board[ny][nx] == '6') break;
if(board[ny][nx] == '0')
board[ny][nx] = '#';
y = ny;
x = nx;
}
}
}else if(val == '5'){
for(int k=0;k<7;k+=2)
{
y = v[depth].first;
x = v[depth].second;
while(true)
{
int nx = x + c5[k];
int ny = y + c5[k+1];
if(nx<0 or ny<0 or nx>=M or ny>=N) break;;
if(board[ny][nx] == '6') break;
if(board[ny][nx] == '0')
board[ny][nx] = '#';
y = ny;
x = nx;
}
}
}
func(depth+1,board,0,0,0,0);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
cin >> origin[i][j];
if(origin[i][j]>='1' and origin[i][j]<='5')
v.push_back({i,j});
}
func(0, origin, 0,0,0,0);
cout << ans;
return 0;
}
- 느낀 점
- 각 cctv별로
방향
을 정해주는 과정이 복잡함 --> 뒤 풀이에서 단순하게 처리
재귀
를 쓰다보니 board[][]
를 값만 복사하기 위해 새로 만든 뒤 일일이 복사함
[ 최적 풀이 ]
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
int N,M,ans=1e9;
vector<pair<int,int>> cctv;
char board1[10][10];
char board2[10][10];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
void upd(int y, int x, int dir){
dir %= 4;
while(true){
x += dx[dir];
y += dy[dir];
if((x<0 or y<0 or x>=M or y>=N) or board2[y][x] == '6') return;
if(board2[y][x] != '0') continue;
board2[y][x] = '#';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
cin >> board1[i][j];
if(board1[i][j] >= '1' and board1[i][j] <= '5')
cctv.push_back({i,j});
}
for(int tmp=0;tmp<(1<<(2*cctv.size()));tmp++)
{
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
board2[i][j] = board1[i][j];
int brute = tmp;
for(int i=0;i<cctv.size();i++)
{
int dir = brute%4;
brute /= 4;
int y = cctv[i].first;
int x = cctv[i].second;
if(board1[y][x] == '1'){
upd(y,x,dir);
}else if(board1[y][x] == '2'){
upd(y,x,dir);
upd(y,x,dir+2);
}else if(board1[y][x] == '3'){
upd(y,x,dir);
upd(y,x,dir+1);
}else if(board1[y][x] == '4'){
upd(y,x,dir);
upd(y,x,dir+1);
upd(y,x,dir+2);
}else if(board1[y][x] == '5'){
upd(y,x,dir);
upd(y,x,dir+1);
upd(y,x,dir+2);
upd(y,x,dir+3);
}
}
int cnt = 0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(board2[i][j] == '0') cnt++;
ans = min(ans,cnt);
}
cout << ans;
return 0;
}
- 핵심
cctv별로 가진 방향의 수
가 다르다 (각자 4,2,4,4,1 가지)
이 때 각 cctv가 4가지의 경우
를 갖는다고 가정하고 4진수로 값을 표현
해서 모든 경우의 수를 구함
ex): 만약, cctv가 3개
라면 각자 4가지 경우를 가지니 4^3
만큼 경우가 나온다고 가정하고 4진수의 값 범위
를 0 ~ 4^3
이라고 할 수 있음
즉, 이것은 일반화 하면 최대를 1<<(2*cctv.size())
로 표현할 수 있다
(1
을 K
만큼 쉬프트 연산
을 하면 2^k
가 된다)
- 각 cctv의 방향은 결국
상/하/좌/우
를 조합해서 실행시키는 것이니까 이것을 처리하는 udp() 함수
생성
(udp(int y, int x, int dir)
)
(dx[] / dy[]
순서를 반드시 '상'과'하'
, '좌'와 '우'
를 붙히면 안됨 --> dir계산
을 할 수 없음)