[BOJ] C++ 15683: 감시 - 백트래킹과 재귀, 시뮬레이션의 전형적인 문제

2023.10.25 - [알고리즘/문제풀이] - [BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹

15683번: 감시

 

예제가 굉장히 많아 백준에서 참고하시길 바랍니다. 주의할 점은 백준의 test case에는 4번 cctv에 대한 검증이 부족하므로 개인적으로 테스트해볼 것을 추천합니다.

---

먼저 문제는 최대 8 * 8 크기에 최대 8개의 cctv 각 cctv는 최대 4방향이므로 4^8 = 65536이다. 따라서 완전탐색으로도 충분히 시간안에 풀 수 있을 것 같아서 완전 탐색으로 기틀을 잡았다. 완전 탐색을 구현하려면 모든 cctv에 대해 모든 방향을 탐색해야 한다. 이 부분에서 다른 재귀 문제들과 유사한 구조가 보여서 재귀로 구현하였다. 아래 문제와 비슷한 방식이다.

[BOJ] C++ 15655 N과 M (6) - 제한이 까다로운 백트래킹

나는 재귀로 구현하기 전에 먼저 함수 정의와 base condition, 재귀식을 짜두고 구현하는 편이다.

 

결론적으로 내린 함수 정의들은 위와 같다. 처음에는 (a, b)의 cctv를 켤 때 사각지대를 계산하는 방식으로 구현했는데, 오히려 더 비효율적이고 어차피 완전 탐색이므로 방향만 미리 설정해 두고 마지막에 사각지대를 계산하는 방식으로 바꿨다.

 

재귀식을 다 짜두고도 구현해야할 부분이 상당히 많은데, 먼저 각 cctv를 방향별로 켜기 위해 상하좌우 일직선 방향을 켜는 함수부터 구성했다.

// 왼쪽 방향 감시 표시
void checkLeftward(int x, int y)
{
    for (int ny = y - 1; ny >= 0; ny--)
    {
        if (space[x][ny] == 6)
            break;
        if (space[x][ny] >= 1 && space[x][ny] <= 5)
            continue;
        space[x][ny] = -1;
    }
}

// 오른쪽 방향 감시 표시
void checkRightward(int x, int y)
{
    for (int ny = y + 1; ny < m; ny++)
    {
        if (space[x][ny] == 6)
            break;
        if (space[x][ny] >= 1 && space[x][ny] <= 5)
            continue;
        space[x][ny] = -1;
    }
}

// 위쪽 방향 감시 표시
void checkUpward(int x, int y)
{
    for (int nx = x - 1; nx >= 0; nx--)
    {
        if (space[nx][y] == 6)
            break;
        if (space[nx][y] >= 1 && space[nx][y] <= 5)
            continue;
        space[nx][y] = -1;
    }
}

// 아래쪽 방향 감시 표시
void checkDownward(int x, int y)
{
    for (int nx = x + 1; nx < n; nx++)
    {
        if (space[nx][y] == 6)
            break;
        if (space[nx][y] >= 1 && space[nx][y] <= 5)
            continue;
        space[nx][y] = -1;
    }
}

 

그리고 각 cctv를 켜는 함수를 구성했는데, 이 부분은 딱히 헷갈리는 부분 없이 cctv를 켤 방향을 k로 받아서 k 방향에 맞게 켜는 방식으로 구성했다.

void turn1(int dir, int a, int b)
{
    //(a, b)의 1번 cctv를 dir 방향으로 켠다. dir은 상하좌우 차례로 0 1 2 3 이다.
    switch (dir)
    {
    case 0:
        // 윗 방향으로 켜기
        checkUpward(a, b);
        break;
    case 1:
        // 아랫 방향
        checkDownward(a, b);
        break;
    case 2:
        // 왼쪽
        checkLeftward(a, b);
        break;
    case 3:
        // 오른쪽
        checkRightward(a, b);
        break;
    }
}

void turn2(int dir, int a, int b)
{
    //(a, b)의 2번 cctv를 dir 방향으로 켠다. dir은 상하/좌우 차례로 0, 1이다.
    switch (dir)
    {
    case 0:
        // 상하
        checkUpward(a, b);
        checkDownward(a, b);
        break;
    case 1:
        // 좌우
        checkLeftward(a, b);
        checkRightward(a, b);
        break;
    }
}

void turn3(int dir, int a, int b)
{
    //(a, b)의 3번 cctv를 dir 방향으로 켠다. dir은 상하좌우 차례로 0 1 2 3 이다.
    switch (dir)
    {
    case 0:
        // 상 우
        checkUpward(a, b);
        checkRightward(a, b);
        break;
    case 1:
        // 하 좌
        checkDownward(a, b);
        checkLeftward(a, b);
        break;
    case 2:
        // 좌 상
        checkLeftward(a, b);
        checkUpward(a, b);
        break;
    case 3:
        // 우 하
        checkRightward(a, b);
        checkDownward(a, b);
        break;
    }
}

void turn4(int dir, int a, int b)
{
    //(a, b)의 4번 cctv를 dir을 제외한 방향으로 켠다. dir은 상하좌우 차례로 0 1 2 3 이다.
    switch (dir)
    {
    case 0:
        // 상 제외
        checkDownward(a, b);
        checkLeftward(a, b);
        checkRightward(a, b);
        break;
    case 1:
        // 하 제외
        checkUpward(a, b);
        checkLeftward(a, b);
        checkRightward(a, b);
        break;
    case 2:
        // 좌 제외
        checkDownward(a, b);
        checkUpward(a, b);
        checkRightward(a, b);
        break;
    case 3:
        // 우 제외
        checkDownward(a, b);
        checkLeftward(a, b);
        checkUpward(a, b);
        break;
    }
}

void turn5(int a, int b)
{
    //(a, b)의 5번 cctv를 켠다.
    checkUpward(a, b);
    checkDownward(a, b);
    checkLeftward(a, b);
    checkRightward(a, b);
}

 

이제 메인 재귀 함수인 func를 짜야하는데, func함수의 기본적인 구성은 아래와 같다.

1. base condition : if(cnt == cctv) 사각지대 계산 후 종료
2. 재귀식 : 방문하지 않은 다음 cctv nX, nY를 찾는다.
   -> func(nX, nY) 호출이 끝나면 다시 (a, b)의 cctv를 꺼야 하므로 space를 임시로 저장해 둔다.
   -> (a, b)의 cctv를 켜고(방향 표시, 켠 부분을 -1로 기록하였다.) func(nX, nY, cnt+1) 호출
   -> func의 호출이 끝나면 (nX, nY)를 다시 미방문처리해 줘야 정상적으로 작동한다.
   ->(a, b)의 cctv를 끈 상태로 space 복구

void func(int a, int b, int cnt)
{
    // a, b의 cctv를 켠다. 현재 cnt만큼의 cctv를 켰다.
    if (cnt == cctv)
    {
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (space[i][j] == 0)
                    res++;
        if (res < min_res)
            min_res = res;
   
    }

    // cctv를 끈 후 space를 원상복구하기 위해 임시로 저장
    int tmp_arr[10][10];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            tmp_arr[i][j] = space[i][j];

    visited[a][b] = true;

    int nX = -1, nY = -1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (space[i][j] >= 1 && space[i][j] <= 5 && visited[i][j] == 0)
            {
                nX = i;
                nY = j;
                break;
            }
        if (nX != -1)
            break;
    }

    switch (space[a][b])
    {
    case 1:
        // (a, b)의 cctv를 켠다.
        // func(nX, nY, cnt+1) 호출 이후 다시 space를 복구시킨다. 모든 방향에 대해 반복한다.
        for (int k = 0; k < 4; k++)
        {
            turn1(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 2:
        for (int k = 0; k < 2; k++)
        {
            turn2(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 3:
        for (int k = 0; k < 4; k++)
        {
            turn3(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 4:
        for (int k = 0; k < 4; k++)
        {
            turn4(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 5:
        turn5(a, b);
        func(nX, nY, cnt + 1);
        visited[nX][nY] = false;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                space[i][j] = tmp_arr[i][j];
    }
}

 

이렇게 구현해 준 것들을 합치면 아래와 같다. 구현해야 할 함수들이 워낙 많아서 잔실수가 나오기 쉽다. 처음에 기본 구조를 잘 짜두고 풀집중상태로 구현해 주는 것이 키포인트이다.

/** 시뮬레이션 15683 감시 **/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int space[10][10];
bool visited[10][10];
int cctv = 0;
int min_res = 1000;

// 왼쪽 방향 감시 표시
void checkLeftward(int x, int y)
{
    for (int ny = y - 1; ny >= 0; ny--)
    {
        if (space[x][ny] == 6)
            break;
        if (space[x][ny] >= 1 && space[x][ny] <= 5)
            continue;
        space[x][ny] = -1;
    }
}

// 오른쪽 방향 감시 표시
void checkRightward(int x, int y)
{
    for (int ny = y + 1; ny < m; ny++)
    {
        if (space[x][ny] == 6)
            break;
        if (space[x][ny] >= 1 && space[x][ny] <= 5)
            continue;
        space[x][ny] = -1;
    }
}

// 위쪽 방향 감시 표시
void checkUpward(int x, int y)
{
    for (int nx = x - 1; nx >= 0; nx--)
    {
        if (space[nx][y] == 6)
            break;
        if (space[nx][y] >= 1 && space[nx][y] <= 5)
            continue;
        space[nx][y] = -1;
    }
}

// 아래쪽 방향 감시 표시
void checkDownward(int x, int y)
{
    for (int nx = x + 1; nx < n; nx++)
    {
        if (space[nx][y] == 6)
            break;
        if (space[nx][y] >= 1 && space[nx][y] <= 5)
            continue;
        space[nx][y] = -1;
    }
}

void turn1(int dir, int a, int b)
{
    //(a, b)의 1번 cctv를 dir 방향으로 켠다. dir은 상하좌우 차례로 0 1 2 3 이다.
    switch (dir)
    {
    case 0:
        // 윗 방향으로 켜기
        checkUpward(a, b);
        break;
    case 1:
        // 아랫 방향
        checkDownward(a, b);
        break;
    case 2:
        // 왼쪽
        checkLeftward(a, b);
        break;
    case 3:
        // 오른쪽
        checkRightward(a, b);
        break;
    }
}

void turn2(int dir, int a, int b)
{
    //(a, b)의 2번 cctv를 dir 방향으로 켠다. dir은 상하/좌우 차례로 0, 1이다.
    switch (dir)
    {
    case 0:
        // 상하
        checkUpward(a, b);
        checkDownward(a, b);
        break;
    case 1:
        // 좌우
        checkLeftward(a, b);
        checkRightward(a, b);
        break;
    }
}

void turn3(int dir, int a, int b)
{
    //(a, b)의 3번 cctv를 dir 방향으로 켠다. dir은 상하좌우 차례로 0 1 2 3 이다.
    switch (dir)
    {
    case 0:
        // 상 우
        checkUpward(a, b);
        checkRightward(a, b);
        break;
    case 1:
        // 하 좌
        checkDownward(a, b);
        checkLeftward(a, b);
        break;
    case 2:
        // 좌 상
        checkLeftward(a, b);
        checkUpward(a, b);
        break;
    case 3:
        // 우 하
        checkRightward(a, b);
        checkDownward(a, b);
        break;
    }
}

void turn4(int dir, int a, int b)
{
    //(a, b)의 4번 cctv를 dir을 제외한 방향으로 켠다. dir은 상하좌우 차례로 0 1 2 3 이다.
    switch (dir)
    {
    case 0:
        // 상 제외
        checkDownward(a, b);
        checkLeftward(a, b);
        checkRightward(a, b);
        break;
    case 1:
        // 하 제외
        checkUpward(a, b);
        checkLeftward(a, b);
        checkRightward(a, b);
        break;
    case 2:
        // 좌 제외
        checkDownward(a, b);
        checkUpward(a, b);
        checkRightward(a, b);
        break;
    case 3:
        // 우 제외
        checkDownward(a, b);
        checkLeftward(a, b);
        checkUpward(a, b);
        break;
    }
}

void turn5(int a, int b)
{
    //(a, b)의 5번 cctv를 켠다.
    checkUpward(a, b);
    checkDownward(a, b);
    checkLeftward(a, b);
    checkRightward(a, b);
}

void func(int a, int b, int cnt)
{
    // a, b의 cctv를 켠다. 현재 cnt만큼의 cctv를 켰다.
    if (cnt == cctv)
    {
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (space[i][j] == 0)
                    res++;
        if (res < min_res)
            min_res = res;
   
    }

    // cctv를 끈 후 space를 원상복구하기 위해 임시로 저장
    int tmp_arr[10][10];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            tmp_arr[i][j] = space[i][j];

    visited[a][b] = true;

    int nX = -1, nY = -1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            if (space[i][j] >= 1 && space[i][j] <= 5 && visited[i][j] == 0)
            {
                nX = i;
                nY = j;
                break;
            }
        if (nX != -1)
            break;
    }

    switch (space[a][b])
    {
    case 1:
        // (a, b)의 cctv를 켠다.
        // func(nX, nY, cnt+1) 호출 이후 다시 space를 복구시킨다. 모든 방향에 대해 반복한다.
        for (int k = 0; k < 4; k++)
        {
            turn1(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 2:
        for (int k = 0; k < 2; k++)
        {
            turn2(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 3:
        for (int k = 0; k < 4; k++)
        {
            turn3(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 4:
        for (int k = 0; k < 4; k++)
        {
            turn4(k, a, b);
            func(nX, nY, cnt + 1);
            visited[nX][nY] = false;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    space[i][j] = tmp_arr[i][j];
        }
        break;
    case 5:
        turn5(a, b);
        func(nX, nY, cnt + 1);
        visited[nX][nY] = false;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                space[i][j] = tmp_arr[i][j];
    }
}

int main()
{
    ios_base::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 >> space[i][j];
            if (space[i][j] != 0 && space[i][j] != 6)
                cctv++;
        }

    int x = -1, y = -1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (space[i][j] >= 1 && space[i][j] <= 5)
            {
                x = i;
                y = j;
                break;
            }
        }
        if (x != -1)
            break;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            visited[i][j] = false;
    func(x, y, 0);

    cout << min_res;
}