[C++] BOJ 15683번: 감시

문제 링크

문제 설명

총 5종류의 CCTV가 문제에서 주어지고, CCTV의 배치도가 주어졌을 때 CCTV 사각지대의 최소 개수를 구하는 문제이다.

M, N이 8 이하로 작기 때문에 백트래킹을 이용하여 문제를 풀어보았다. DFS 문제를 풀 때와 비슷하게 dx, dy 상수를 만들어 이동 방향을 설정해주었다.

문제를 읽을 때 "CCTV는 CCTV를 통과할 수 있다." 라는 부분을 읽지 못하여 여러 번 틀리면서 제출하였다. 문제를 주의 깊게 읽을 필요성을 느꼈다.

코드가 많이 길어졌는데 더 간결하게 작성할 방법을 찾아볼 필요가 있어보인다.

코드

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

// 문제에서 제시한 0~6의 숫자
#define EMPTY 0
#define WALL 6
#define ONE 1
#define TWO 2
#define THREE 3
#define FOUR 4
#define FIVE 5

// CCTV가 한 번 이상 본 위치는 WATCHED 이상의 값으로 설정함
#define WATCHED 7

using namespace std;

int N, M;

int map[12][12];
int emptycnt = 0;

vector<pair<int, int>> cctvpos;
vector<int> input;

// 초기의 result 값을 M * N보다 큰 값으로 두었음. 이 코드에서 실제로 9999라는 값이 출력되는 일은 없음.
int result = 9999;

// 이동 방향 설정
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

void checkStraightLine(pair<int, int> &pos, int dir)
{
    int x = pos.first;
    int y = pos.second;

    while (true)
    {
        x += dx[dir];
        y += dy[dir];
        if (x < 0 || y < 0 || x >= M || y >= N) // (0,0)부터 (M-1,N-1) 사이를 넘어선 영역에 도달하면 break
            break;
        if (map[x][y] == WALL) // 벽에 가로막히면 break
            break;
        if (ONE <= map[x][y] && map[x][y] <= FIVE)
            continue; // CCTV는 다른 CCTV 너머를 볼 수 있기 때문에 break 대신 continue 사용.

        if (map[x][y] >= WATCHED) // 이미 다른 CCTV가 본 곳을 중복해서 보았을 경우 해당 위치의 값을 1 증가시킴.
        {
            map[x][y] += 1;
        }
        else if (map[x][y] == EMPTY) // 아직 다른 CCTV가 보지 않은 EMPTY일 경우 해당 위치의 값을 WATCHED로 바꿈.
        {
            map[x][y] = WATCHED;
            emptycnt--; // EMPTY인 공간이 1칸 줄어들었으므로 emptycnt 값 1 감소.
        }
    }
}

void uncheckStraightLine(pair<int, int> &pos, int dir)
{
    int x = pos.first;
    int y = pos.second;

    while (true)
    {
        x += dx[dir];
        y += dy[dir];
        if (x < 0 || y < 0 || x >= M || y >= N) // (0,0)부터 (M-1,N-1) 사이를 넘어선 영역에 도달하면 break
            break;
        if (map[x][y] == WALL) // 벽에 가로막히면 break
            break;
        if (ONE <= map[x][y] && map[x][y] <= FIVE) // CCTV는 다른 CCTV 너머를 볼 수 있기 때문에 break 대신 continue 사용.
            continue;
        if (map[x][y] > WATCHED) // 이미 다른 CCTV가 중복해서 본 곳이므로 값을 1 감소시킴.
        {
            map[x][y] -= 1;
        }
        else if (map[x][y] == WATCHED)
        {
            map[x][y] = EMPTY;
            emptycnt++; // EMPTY인 공간이 1칸 늘어났으므로 emptycnt 값 1 증가.
        }
    }
}

// dir을 이용하여 각도를 표현함. 0은 0도, 1은 90도, 2는 180도, 3은 270도 회전을 의미.
void checkOne(pair<int, int> &pos, int dir)
{
    checkStraightLine(pos, dir);
}

void checkTwo(pair<int, int> &pos, int dir)
{
    checkStraightLine(pos, dir);
    checkStraightLine(pos, (dir + 2) % 4);
}

void checkThree(pair<int, int> &pos, int dir)
{
    checkStraightLine(pos, dir);
    checkStraightLine(pos, (dir + 1) % 4);
}

void checkFour(pair<int, int> &pos, int dir)
{
    checkStraightLine(pos, dir);
    checkStraightLine(pos, (dir + 1) % 4);
    checkStraightLine(pos, (dir + 2) % 4);
}

void checkFive(pair<int, int> &pos)
{
    checkStraightLine(pos, 0);
    checkStraightLine(pos, 1);
    checkStraightLine(pos, 2);
    checkStraightLine(pos, 3);
}

void uncheckOne(pair<int, int> &pos, int dir)
{
    uncheckStraightLine(pos, dir);
}

void uncheckTwo(pair<int, int> &pos, int dir)
{
    uncheckStraightLine(pos, dir);
    uncheckStraightLine(pos, (dir + 2) % 4);
}

void uncheckThree(pair<int, int> &pos, int dir)
{
    uncheckStraightLine(pos, dir);
    uncheckStraightLine(pos, (dir + 1) % 4);
}

void uncheckFour(pair<int, int> &pos, int dir)
{
    uncheckStraightLine(pos, dir);
    uncheckStraightLine(pos, (dir + 1) % 4);
    uncheckStraightLine(pos, (dir + 2) % 4);
}

void uncheckFive(pair<int, int> &pos)
{
    uncheckStraightLine(pos, 0);
    uncheckStraightLine(pos, 1);
    uncheckStraightLine(pos, 2);
    uncheckStraightLine(pos, 3);
}

void calcArea(int depth)
{
    if (depth >= input.size())
    {
        if (emptycnt < result)
        {
            result = emptycnt;
        }
        return;
    }

    switch (input[depth])
    {
    case ONE:
        for (int i = 0; i < 4; i++)
        {
            checkOne(cctvpos[depth], i);
            calcArea(depth + 1);
            uncheckOne(cctvpos[depth], i);
        }
        break;
    case TWO:
        for (int i = 0; i < 2; i++)
        {
            checkTwo(cctvpos[depth], i);
            calcArea(depth + 1);
            uncheckTwo(cctvpos[depth], i);
        }
        break;
    case THREE:
        for (int i = 0; i < 4; i++)
        {
            checkThree(cctvpos[depth], i);
            calcArea(depth + 1);
            uncheckThree(cctvpos[depth], i);
        }
        break;
    case FOUR:
        for (int i = 0; i < 4; i++)
        {
            checkFour(cctvpos[depth], i);
            calcArea(depth + 1);
            uncheckFour(cctvpos[depth], i);
        }
        break;
    case FIVE:
        checkFive(cctvpos[depth]);
        calcArea(depth + 1);
        uncheckFive(cctvpos[depth]);
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[j][i];
            if (map[j][i] != EMPTY && map[j][i] != WALL)
            {
                cctvpos.push_back({j, i});
                input.push_back(map[j][i]);
            }
            if (map[j][i] == EMPTY)
            {
                emptycnt++;
            }
        }
    }

    calcArea(0);
    cout << result << '\n';

    return 0;
}