[C++][백준 15683] 감시

[문제]

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

15683번: 감시

[문제 풀이]

https://youtu.be/jZwf4OPlhtk

바킹덕님 영상을 보고 참고해서 풀었었다.

처음에는 cctv의 숫자 1,2,3,4,5일때 모두 함수를 다르게 해서 풀려고 했었으나 해당 영상을 보고 하나의 함수를 이용해 1,2,3,4,5일때 함수(방향), 함수(방향 + 1), 함수(방향 + 2) 식으로 해당 cctv에서의 동작을 파악했다.

//x,y는 좌표, dir은 방향(0,1,2,3)
//board2는 board 배열의 카피본
//oob(x,y)는 x,y좌표가 board의 끝에 다다른건지 확인 하는 함수

void ups(int x,int y,int dir){
	dir %= 4;
    while(true){
    x += dx[dir];
    y += dy[dir];
    //만일, 벽에 마주치거나 board크기의 끝에 다다른다면
    if(oob(x,y) || board[x][y] == 6){
	    return;
    }
    if(board[x][y] != 0){
    	continue;
    }
    board2[x][y] = 7;
    }
}

다만, 바킹덕님은 4진법을 이용해서 문제를 풀었는데 나는 실제 상황에서 그렇게 머리를 돌릴 수는 없을 것 같애서 재귀를 사용해서 순열을 먼저 만들어두고 풀었다.

[회고]

1. dx[]와 dy[]의 순서가 중요하다. 처음에 해당 순서를 잘못 배치했다가 틀렸습니다를 얻었다.

2. dir %=4 에 주의하도록 하자. 4로 나누지 않으면 dir + 3으로 보냈다가 오류가 발생할 수 있다. 순열로 ( 0 ~ 3) 까지만 얻어서 문제가 없을거라고 생각했는데 안에 들어갈때 dir + 3으로 6이 되어서 오류가 발생해 시간초과가 발생했다.

3.

bool OOP(int x,int y){
	return (x < 0 || x>=n || y<0 || y>=m);
}

을 잘 이용하도록 하자. 해당 함수가 없을때 비슷한 문제를 풀었다가 코드가 너무 길어져서 힘들었던 경험이 있다.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"

using namespace std;

vector<pair<int,int> > cctv;
vector<vector<int> > perm;
vector<int> recursive;
int board[10][10];
int board2[10][10];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int n,m;

void dfs(){
    if(recursive.size() == cctv.size()){
        perm.push_back(recursive);
        return;
    }

    for(int i = 0;i<4;i++){
        recursive.push_back(i);
        dfs();
        recursive.pop_back();
    }
    return;
}

//board배열을 graph배열과 일치시키자.
void boardEqual(){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            board2[i][j] = board[i][j];
        }
    }
    return;
}

//board2 배열 내부에 0이 몇개 있는지 파악하자.
int boardCheck(){
    int answer = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(board2[i][j] == 0){
                answer++;
            }
        }
    }
    return answer;
}

bool OOP(int x,int y){
    return x<0 || x>= n || y <0 || y>=m;
}

void ups(int x, int y, int dir){
    dir %= 4;
    while(true){
        x += dx[dir];
        y += dy[dir];
        if(OOP(x,y) || board2[x][y] == 6){
            return;
        }
        if(board2[x][y] != 0){
            continue;
        }
        board2[x][y] = 7;
    }
    return;
}

int main(){
    cin>>n>>m;

    //0이 몇개 들어있는지 세는 변수.
    int total = 0;

    //입력 받자.
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>board[i][j];
            //만일 0이나 6이 아니라면 cctv이니 cctv에 좌표를 넣자.
            if(board[i][j] != 0 && board[i][j] != 6){
                cctv.push_back(make_pair(i,j));
            }
            //만일 0이라면 total에 총 몇개가 들어가는지 세자.
            if(board[i][j] == 0){
                total++;
            }
        }
    }

    //재귀를 이용해서 0~3까지 cctv.size()만큼 가져오자.(완탐으로 조합 만들기)
    dfs();

    for(int i = 0;i<perm.size();i++){
        boardEqual();

        for(int j = 0;j<cctv.size();j++){
            //dir는 perm[i][j] => perm은 순열이 들어있는 이차원 배열. perm[0] => {0,0,0}, perm[1] => {0,0,1} 식.
            int dir = perm[i][j];
            //x,y는 cctv[j]의 요소. j => cctv의 숫자.
            int x = cctv[j].first;
            int y = cctv[j].second;

            if(board[x][y] == 1){
                ups(x,y,dir);
            }
            else if(board[x][y] == 2){
                ups(x,y,dir);
                ups(x,y,dir+2);
            }
            else if(board[x][y] == 3){
                ups(x,y,dir);
                ups(x,y,dir+1);
            }
            else if(board[x][y] == 4){
                ups(x,y,dir);
                ups(x,y,dir+1);
                ups(x,y,dir+2);
            }
            else if(board[x][y] == 5){
                ups(x,y,dir);
                ups(x,y,dir+1);
                ups(x,y,dir+2);
                ups(x,y,dir+3);
            }
        }

        int val;
        val = boardCheck();
        total = min(total,val);
    }

    cout<<total<<endl;

    return 0;
}