BOJ 15683 : 감시 - C++
감시
코드
[ 간신히 푼 코드 ]
#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; // 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;
/* cctv는 건너가기 위해 */
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});
}
/* 로직 시작 - cctv수가 4개면 총 4^4만큼 돌아야 함
즉, (cctv수*2)만큼 1을 왼쪽 쉬프트 하면 4^(cctv수)가 된다 */
for(int tmp=0;tmp<(1<<(2*cctv.size()));tmp++)
{
/* board1 복사 */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
board2[i][j] = board1[i][j];
int brute = tmp;
/* cctv개수만큼 반복 */
for(int i=0;i<cctv.size();i++)
{
/* cctv방향이 최대 4가지이므로 4진법으로 해서 일의자리를 하나씩 추출
--> 만약 cctv가 3개이면 000 ~ 333까지 총 4^3만큼의 경우를 실행 */
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계산
을 할 수 없음)
Author And Source
이 문제에 관하여(BOJ 15683 : 감시 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-15683-감시-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
[ 간신히 푼 코드 ]
#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; // 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; /* cctv는 건너가기 위해 */ 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}); } /* 로직 시작 - cctv수가 4개면 총 4^4만큼 돌아야 함 즉, (cctv수*2)만큼 1을 왼쪽 쉬프트 하면 4^(cctv수)가 된다 */ for(int tmp=0;tmp<(1<<(2*cctv.size()));tmp++) { /* board1 복사 */ for(int i=0;i<N;i++) for(int j=0;j<M;j++) board2[i][j] = board1[i][j]; int brute = tmp; /* cctv개수만큼 반복 */ for(int i=0;i<cctv.size();i++) { /* cctv방향이 최대 4가지이므로 4진법으로 해서 일의자리를 하나씩 추출 --> 만약 cctv가 3개이면 000 ~ 333까지 총 4^3만큼의 경우를 실행 */ 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계산
을 할 수 없음)
Author And Source
이 문제에 관하여(BOJ 15683 : 감시 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-15683-감시-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)