백준 15683. 감시 (백트래킹, 구현)

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

15683번: 감시

감시카메라들이 볼 수 있는 방향들을 모두 탐색해야하므로 백트래킹을 사용했다. 

ex. 1번, 2번 감시 카메라가 있는 경우 

(1번, 2번) -> (상, 수평), (하, 수평), (좌, 수평), (우, 수평), (상, 수직), (하, 수직), (좌, 수직), (우, 수직)

 

1.  삽질 포인트

1) left, up 함수 구현:

x와 y값의 근접값부터 -1 표시를 했어야하는데, x와 y를 0부터 -1 표시해서 벽넘어서까지도 -1로 초기화 해버렸다. 

 

2. 특징

1) func함수가 이 문제에 핵심 -> 백트래킹

각 cctv별로 볼 수 있는 곳의 개수가 다르다. 볼 수 있는 곳에 대한 순서열을 만든다. 

 

2) 구현

drawfunc: 순서열이 다 만들어지면, 이에 따라 볼 수 있는 곳을 board에 표시해준다. (board[][] = -1)

countfunc: 볼 수 없는 곳((board[][] == 0) 의 개수를 센다.

 

3. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <set>
#include <cstring>
#include <string>
#include <stdio.h>
#include <limits.h>
//#include <bits/stdc++.h>
using namespace std;


int n, m;
int qsize;
int wsize;
int input[10][10];
int board[10][10];
tuple<int, int, int> arr[10];
pair<int, int> ans[10];
pair<int, int> wall[70];
int mn = INT_MAX;

void Right(int x, int y)
{
    for(int i = y + 1; i < m; i++)
    {
        if(board[x][i] == 6)
        {
            return;
        }
        else
        {
            if(board[x][i] <= 5 && board[x][i] >= 1) continue;
            board[x][i] = -1;
        }
    }
}

void Left(int x, int y)
{
    for(int i = y-1; i >= 0; i--)
    {
        if(board[x][i] == 6)
        {
            return;
        }
        else
        {
            if(board[x][i] <= 5 && board[x][i] >= 1) continue;
            board[x][i] = -1;
        }
    }
}

void Up(int x, int y)
{
    for(int i = x - 1; i >= 0; i--)
    {
        if(board[i][y] == 6)
        {
            return;
        }
        else
        {
            if(board[i][y] <= 5 && board[i][y] >= 1) continue;
            board[i][y] = -1;
        }
    }
}

void Down(int x, int y)
{
    for(int i = x + 1; i <n; i++)
    {
        if(board[i][y] == 6)
        {
            return;
        }
        else
        {
            if(board[i][y] <= 5 && board[i][y] >= 1) continue;
            board[i][y] = -1;
        }
    }
}

void drawfunc()
{
    //board 초기화
    for(int i = 0; i < n; i++)
    {
        fill(board[i], board[i] + m, 0);
    }
    for(int i = 0; i < wsize; i++)
    {
        int x = wall[i].first;
        int y = wall[i].second;

        board[x][y] = 6;
    }

    for(int i = 0; i < qsize; i++)
    {
        int x = get<0>(arr[i]);
        int y = get<1>(arr[i]);

        board[x][y] = get<2>(arr[i]);
    }

    for(int i = 0; i < qsize; i++)
    {
        int cameranum = ans[i].second;
        int dir = ans[i].first;
        int x = get<0>(arr[i]);
        int y = get<1>(arr[i]);

        if(cameranum == 1)
        {
            if(dir == 0) { Right(x, y); }
            if(dir == 1) { Left(x, y); }
            if(dir == 2) { Up(x, y); }
            if(dir == 3){ Down(x, y); }
        }
        if(cameranum == 2)
        {
            if(dir == 0) { Right(x, y); Left(x, y);}
            if(dir ==1) { Up(x, y); Down(x, y);}
        }
        if(cameranum == 3)
        {
            if(dir == 0){ Up(x,y); Right(x, y); }
            if(dir == 1) { Right(x, y); Down(x, y);}
            if(dir == 2) { Down(x, y); Left(x, y); }
            if(dir == 3) { Left(x, y); Up(x, y); }
        }
        if(cameranum == 4)
        {
            if(dir == 0){ Left(x, y); Up(x,y); Right(x, y); }
            if(dir == 1){ Up(x,y); Right(x, y); Down(x, y); }
            if(dir == 2){ Right(x, y); Down(x, y); Left(x, y); }
            if(dir == 3){ Down(x, y); Left(x, y); Up(x,y); }
        }
        if(cameranum == 5){ Right(x, y); Left(x, y); Up(x, y);Down(x, y); }
    }
}

void printfunc()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << endl;
}

void countfunc()
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(board[i][j] == 0) cnt++;
        }
    }
    mn = min(mn, cnt);
}


void func(int cur)
{
    if(cur == qsize)
    {
        // 보드에 그림그리고 0의 개수 세기
        drawfunc();
        //printfunc();
        countfunc();

        return;
    }
    int pointer = 0;

    while(1)
    {
        if(get<2>(arr[cur]) == 1 && pointer >= 4) return;
        if(get<2>(arr[cur]) == 2 && pointer >= 2) return;
        if(get<2>(arr[cur]) == 3 && pointer >= 4) return;
        if(get<2>(arr[cur]) == 4 && pointer >= 4) return;
        if(get<2>(arr[cur]) == 5 && pointer >= 1) return;

        ans[cur] = make_pair(pointer, get<2>(arr[cur])); // 순서, 카메라 넘버
        pointer++;
        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++)
        {
            int x;
            cin >> x;
            input[i][j] = x;
            if(x >= 1 && x <=5)
            {
                arr[qsize] = make_tuple(i, j, x);
                qsize++;

            }   
            if(x == 6)// 벽
            {
                wall[wsize] = make_pair(i, j);
                wsize++;
            }
        }
    }


    func(0);
    cout << mn;
}