[C++] BOJ 15683 / 시뮬레이션 (감시, 첫 시뮬레이션 노가다 경험)

문제 분석

 

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

5가지 종류의 CCTV가 배치되어 있고, 각 CCTV는 감시하는 방향이 다르지만, 회전 시킬 수 있다. CCTV의 배치도가 주어졌을 때의 사각 지대의 최소 크기를 출력하는 문제이다.

CCTV가 감시할 수 있는 방향이 정해져있으며, 회전 시 킬 수 있는 경우의 수는 1번 CCTV부터 차례로 4 2 4 4 1 이다. 회전 시킬 수 있는 모든 경우의 수를 따지고, 그 중 사각 지대가 가장 적을 때를 출력하면 된다.

 

해결 방법

시뮬레이션 문제라서, 따로 해결 방법이라고 할 것이 없다. 문제에 주어진 조건을 충실히 지키며 구현하면 된다.

 

코드

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
#define X first
#define Y second
int n,m;
int board[9][9];
int tmpBoard[9][9];
int arr[5] = {0,0,0,0,1};
int ans = 81;
vector<pair<int,int>> v;
vector<pair<int,int>> cctv;
void watchLeft(int x, int y) {
    for(int curY=y-1;curY>=0;curY--) {
        if(tmpBoard[x][curY] == 6) break;
        else if(tmpBoard[x][curY] == 0)
            tmpBoard[x][curY] = 1;
        else continue;
    }
}
void watchRight(int x, int y) {
    for(int curY=y+1;curY<=m;curY++) {
        if(tmpBoard[x][curY] == 6) break;
        else if(tmpBoard[x][curY] == 0)
            tmpBoard[x][curY] = 1;
        else continue;
    }    
}
void watchTop(int x, int y) {
    for(int curX=x-1;curX>=0;curX--) {
        if(tmpBoard[curX][y] == 6) break;
        else if(tmpBoard[curX][y] == 0)
            tmpBoard[curX][y] = 1;
        else continue;
    }    
}
void watchBottom(int x, int y) {
    for(int curX=x+1;curX<=n;curX++) {
        if(tmpBoard[curX][y] == 6) break;
        else if(tmpBoard[curX][y] == 0)
            tmpBoard[curX][y] = 1;
        else continue;
    }    
}
void one(int x, int y, int flag) {
    if(flag == 1) {
        watchTop(x,y);
    }
    else if(flag == 2) {
        watchBottom(x,y);
    }
    else if(flag == 3) {
        watchLeft(x,y);
    }
    else if(flag == 4) {
        watchRight(x,y);
    }
    else {
        cout << "CCTV 1 ERROR \n";
    }
}
void two(int x, int y, int flag) {
    if(flag == 1) {
        watchLeft(x,y);
        watchRight(x,y);
    }
    else if(flag == 2) {
        watchTop(x,y);
        watchBottom(x,y);
    }
    else {
        cout << "CCTV 2 ERROR \n";
    }
}
void three(int x, int y, int flag) {
    if(flag == 1) {
        watchTop(x,y);
        watchRight(x,y);
    }
    else if(flag == 2) {
        watchRight(x,y);
        watchBottom(x,y);
    }
    else if(flag == 3) {
        watchBottom(x,y);
        watchLeft(x,y);
    }
    else if(flag == 4) {
        watchTop(x,y);
        watchLeft(x,y);
    }
    else {
        cout << "CCTV 3 ERROR \n";
    }
}
void four(int x, int y, int flag) {
    if(flag == 1) {
        watchLeft(x,y);
        watchTop(x,y);
        watchRight(x,y);
    }
    else if(flag == 2) {
        watchTop(x,y);
        watchRight(x,y);
        watchBottom(x,y);
    }
    else if(flag == 3) {
        watchRight(x,y);
        watchBottom(x,y);
        watchLeft(x,y);
    }
    else if(flag == 4) {
        watchBottom(x,y);
        watchLeft(x,y);
        watchTop(x,y);
    }
    else {
        cout << "CCTV 4 ERROR \n";
    }
}
void five(int x, int y, int flag) {
    if(flag == 1) {
        watchTop(x,y);
        watchRight(x,y);
        watchBottom(x,y);
        watchLeft(x,y);
    }
    else {
        cout << "CCTV 5 ERROR \n";
    }
}

void copyArr() {
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            tmpBoard[i][j] = board[i][j];
        }
    }
}

void func(int cur) {
    if(cur == v.size()) {
        // cctv 탐색
        copyArr();
        int num=0;
        for(auto e : v) {
            if(cctv[num].X == 1)  {
                one(e.X, e.Y, cctv[num].Y);
            }
            else if(cctv[num].X == 2) {
                two(e.X, e.Y, cctv[num].Y);
            }
            else if(cctv[num].X == 3) {
                three(e.X, e.Y, cctv[num].Y);
            }
            else if(cctv[num].X == 4) {
                four(e.X, e.Y, cctv[num].Y);
            }
            else if(cctv[num].X == 5) {
                five(e.X, e.Y, cctv[num].Y);
            }
            num++;
        }
        int cnt = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(tmpBoard[i][j] == 0) cnt++;
            }
        }
        ans = cnt < ans ? cnt : ans;
        return;
    }
    for(int i=1;i<=4;i++) {
        if(cctv[cur].X == 2) {
            if(i>2) {
                return;
            }
        }
        else if(cctv[cur].X == 5) {
            if(i>1) {
                return;
            }
        }
        cctv[cur].second = i;
        func(cur+1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> board[i][j];
            if(board[i][j] != 0 && board[i][j] != 6) {
                v.push_back({i,j});
                cctv.push_back({board[i][j], 0});
            }
        }
    }
    func(0);
    cout << ans;
}

 

구현 시 주의할 점

일단 시뮬레이션 답게 코드가 길다. 코드가 긴 만큼 구현에 시간이 많이 드는 편인데, 본인은 처음에 생각을 잘못해서 구현을 이상한 방향으로 해버려서 처음부터 다시 짜느라 시간이 두배로 걸렸다.

시뮬레이션 문제를 풀 때는, 먼저 구현하고 생각해야지가 아니라 구현 하기 전에 정확한 검토가 이뤄져야 한다는 것을 깨달았다.