감시

코드

[ 간신히 푼 코드 ]

#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계산을 할 수 없음)