ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • [C++] BOJ 15683번 - 감시
      프로그래밍/알고리즘 PS 2024. 5. 23. 21:05

      학교에서 진행하는 수업에서 어렵다고 생각하는 알고리즘 문제를 공유하고, 문제를 풀어보았다.

       

      문제의 난이도는 골드 3으로, 정답률은 약 45%이다. 시간 제한은 1초이다.

      문제 링크

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

      문제 설명

       사무실에 총 5가지 종류의 CCTV가 설치되어 있다. 각 CCTV는 감시할 수 있는 영역이 제한되어 있는데 벽을 뚫을 수 없고, 90도 회전이 가능하다. 이 때 사무실의 크기와 상태, CCTV의 위치가 주어졌을 때 사각 지대의 최소 크기를 구하는 것이 이번 문제이다.

      문제 분석

       사무실의 상태가 입력으로 들어온다. 먼저 세로 크기 N과 가로 크기 M을 입력받으며 0은 빈칸, 1 ~ 5는 CCTV, 6은 벽을 나타내는 각 칸의 정보가 주어진다.

       해당 입력에 대해 사각 지대의 최소 크기를 구하는 것이 이번 문제이다.

       

       사각 지대의 최소 크기를 구하기 위해서는 모든 cctv가 감시한 경우의 수에 대한 사각 지대의 크기를 확인하고, 그 중 최소 크기의 사각 지대를 구해야 한다. 즉, 브루트 포스로 사각 지대가 나타나는 모든 경우의 수를 확인해야 한다는 뜻이다.

       

       그리고 직관적으로 각 경우의 수를 체크하기에 백트래킹이 적합하다는 느낌이 들어 백트래킹으로 문제를 해결하였다. 첫 cctv부터 마지막 cctv까지 하나 하나의 cctv에 대한 감시 영역에 대한 경우의 수를 백트래킹을 통해 만들어간다.

      문제 풀이

       문제에서 값을 입력받을 때에 먼저 cctv들을 따로 모을 수 있도록 입력 코드를 구성하였다.

      cin >> N >> M;

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        cin >> originalMap[i][j];
        if (1 <= originalMap[i][j] && originalMap[i][j] <= 5)
            cctvPoints.push_back({i, j});
    }
}

       

       만일 입력받은 맵의 상태가 1 ~ 5 (cctv)일 경우, cctvPoints라는 vector 타입에 좌표값을 추가해준다.

       

       이 때 맵의 가로와 세로의 길이는 1 ~ 8이라고 주어졌으므로 originalMap 변수를 포함해 필요한 변수는 아래와 같이 전역 변수로 선언하였다. 답으로 출력할 answer 변수는 일단 큰 값인 987654321을 저장하고, 나중에 최소 사각지대 크기의 값으로 변경하도록 구현하였다.

      int originalMap[10][10];
vector<pair<int, int>> cctvPoints;

int answer = 987654321;
int N, M;

       

       특정 방향을 따라 cctv가 관찰할 수 있는 영역에 '#'을 표기하는 함수도 구현하였다. 함수명은 check이며, cctv의 좌표와 방향(0, 1, 2, 3)을 주면 단방향으로 '#'을 그려준다. 당연하지만 '#'은 벽을 뚫을 수 없다. direction %= 4 코드를 삽입한 이유는 3보다 큰 값이 들어오더라도 정상적으로 코드가 처리되도록 하기 위함이다.

      void check(pair<int, int> &cctvPoint, int direction)
{
    direction %= 4;

    int y = cctvPoint.first;
    int x = cctvPoint.second;

    while (true)
    {
        y += dy[direction];
        x += dx[direction];

        if (x < 0 || x >= M || y < 0 || y >= N)
            break;
        if (originalMap[y][x] == 6)
            break;
        if (originalMap[y][x] == 0)
            originalMap[y][x] = '#';
    }
}
      int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

       

       위와 같이 direction을 활용한 코드를 사용하기 위해서는 dy, dx 변수를 선언해주어야 한다. 이 때, CCTV의 회전을 적절하게 표현하기 위해서는 dy와 dx의 값의 순서를 적절하게 구성해야 한다. 지금은 좌, 하, 우, 상 순으로 구성되어 있다.

      void backtracking(int depth)
{
    pair<int, int> cctvPoint = cctvPoints[depth];
    int y = cctvPoint.first;
    int x = cctvPoint.second;

    int tempMap[10][10];

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            tempMap[i][j] = originalMap[i][j];

    for (int i = 0; i < 4; i++)
    {
        if (originalMap[y][x] == 1)
        {
            check(cctvPoint, i);
        }
        else if (originalMap[y][x] == 2)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 2);
        }
        else if (originalMap[y][x] == 3)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 1);
        }
        else if (originalMap[y][x] == 4)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 1);
            check(cctvPoint, i + 3);
        }
        else if (originalMap[y][x] == 5)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 1);
            check(cctvPoint, i + 2);
            check(cctvPoint, i + 3);
        }

        backtracking(depth + 1);

        for (int p = 0; p < N; p++)
            for (int q = 0; q < M; q++)
                originalMap[p][q] = tempMap[p][q];
    }
}

       

       백트래킹 함수에서는 cctv의 좌표를 읽어와, check 함수를 활용하여 각 가능한 경우의 감시 구조를 만들어낸다. 이 때 for문을 돌리는 이유는 CCTV의 direction 90도 회전을 표현하기 위함이다.

       tempMap 변수를 활용하는 이유는, 백트래킹 함수가 return되어 돌아왔을 때 originalMap이 이전 상태로 돌아오도록 하기 위함이다.

       

       위 코드에는 depth가 적절한 크기가 되었을 때에 대한 처리가 빠져있다. 해당 부분도 코드로 작성하면 다음과 같다.

      if (depth == cctvPoints.size())
{
    int numberOfZero = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (originalMap[i][j] == 0)
                numberOfZero++;
    answer = min(answer, numberOfZero);
    return;
}

      해당 코드는 backtracking 함수 최상단에 위치하는 코드이다. 모든 cctv에 대하여 영역 처리가 끝난 상황을 의미하며, 이 때에는 0의 갯수를 세보고 최소 0의 갯수를 구한 뒤 함수에서 return한다.

       

      전체 코드는 아래와 같다.

      전체 코드

      #include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int originalMap[10][10];
vector<pair<int, int>> cctvPoints;

int answer = 987654321;
int N, M;

int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

void check(pair<int, int> &cctvPoint, int direction)
{
    direction %= 4;

    int y = cctvPoint.first;
    int x = cctvPoint.second;

    while (true)
    {
        y += dy[direction];
        x += dx[direction];

        if (x < 0 || x >= M || y < 0 || y >= N)
            break;
        if (originalMap[y][x] == 6)
            break;
        if (originalMap[y][x] == 0)
            originalMap[y][x] = '#';
    }
}

void backtracking(int depth)
{
    if (depth == cctvPoints.size())
    {
        int numberOfZero = 0;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (originalMap[i][j] == 0)
                    numberOfZero++;
        answer = min(answer, numberOfZero);
        return;
    }

    pair<int, int> cctvPoint = cctvPoints[depth];
    int y = cctvPoint.first;
    int x = cctvPoint.second;

    int tempMap[10][10];

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            tempMap[i][j] = originalMap[i][j];

    for (int i = 0; i < 4; i++)
    {
        if (originalMap[y][x] == 1)
        {
            check(cctvPoint, i);
        }
        else if (originalMap[y][x] == 2)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 2);
        }
        else if (originalMap[y][x] == 3)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 1);
        }
        else if (originalMap[y][x] == 4)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 1);
            check(cctvPoint, i + 3);
        }
        else if (originalMap[y][x] == 5)
        {
            check(cctvPoint, i);
            check(cctvPoint, i + 1);
            check(cctvPoint, i + 2);
            check(cctvPoint, i + 3);
        }

        backtracking(depth + 1);

        for (int p = 0; p < N; p++)
            for (int q = 0; q < M; q++)
                originalMap[p][q] = tempMap[p][q];
    }
}

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 >> originalMap[i][j];
            if (1 <= originalMap[i][j] && originalMap[i][j] <= 5)
                cctvPoints.push_back({i, j});
        }
    }

    backtracking(0);

    cout << answer << '\n';

    return 0;
}

       

      여담

      처음에는 direction을 사용하지 않고 작성한 코드로 문제를 풀고 맞추었는데, 코드가 너무 길고 장황하여 인터넷을 참고하여 정리한 코드가 지금의 코드이다.

       

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

using namespace std;

int originalMap[10][10];
vector<pair<int, int>> cctvPoints;

int answer = 987654321;
int N, M;

void moveRight(pair<int, int> &point, int valueFrom, int valueTo)
{
    int y = point.first;
    int x = point.second;
    int nx = x + 1;
    while (nx < M)
    {
        if (originalMap[y][nx] == 6)
            break;
        if (originalMap[y][nx] == valueFrom)
            originalMap[y][nx] = valueTo;
        nx++;
    }
}

void moveLeft(pair<int, int> &point, int valueFrom, int valueTo)
{
    int y = point.first;
    int x = point.second;
    int nx = x - 1;
    while (nx >= 0)
    {
        if (originalMap[y][nx] == 6)
            break;
        if (originalMap[y][nx] == valueFrom)
            originalMap[y][nx] = valueTo;
        nx--;
    }
}

void moveUp(pair<int, int> &point, int valueFrom, int valueTo)
{
    int y = point.first;
    int x = point.second;
    int ny = y - 1;
    while (ny >= 0)
    {
        if (originalMap[ny][x] == 6)
            break;
        if (originalMap[ny][x] == valueFrom)
            originalMap[ny][x] = valueTo;
        ny--;
    }
}

void moveDown(pair<int, int> &point, int valueFrom, int valueTo)
{
    int y = point.first;
    int x = point.second;
    int ny = y + 1;
    while (ny < N)
    {
        if (originalMap[ny][x] == 6)
            break;
        if (originalMap[ny][x] == valueFrom)
            originalMap[ny][x] = valueTo;
        ny++;
    }
}

void backtracking(int depth)
{
    if (depth == cctvPoints.size())
    {
        int numberOfZero = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < M; j++)
            {
                if (originalMap[i][j] == 0)
                    numberOfZero++;
            }
        }
        answer = min(answer, numberOfZero);
        return;
    }

    pair<int, int> cctvPoint = cctvPoints[depth];
    int y = cctvPoint.first;
    int x = cctvPoint.second;

    int tempMap[10][10];

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            tempMap[i][j] = originalMap[i][j];

    if (originalMap[y][x] == 1)
    {
        moveRight(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveLeft(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveUp(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveDown(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];
    }
    else if (originalMap[y][x] == 2)
    {
        moveLeft(cctvPoint, 0, '#');
        moveRight(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveUp(cctvPoint, 0, '#');
        moveDown(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];
    }
    else if (originalMap[y][x] == 3)
    {
        moveLeft(cctvPoint, 0, '#');
        moveUp(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveLeft(cctvPoint, 0, '#');
        moveDown(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveRight(cctvPoint, 0, '#');
        moveUp(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveRight(cctvPoint, 0, '#');
        moveDown(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[j][i] = tempMap[j][i];
    }
    else if (originalMap[y][x] == 4)
    {
        moveUp(cctvPoint, 0, '#');
        moveLeft(cctvPoint, 0, '#');
        moveRight(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveDown(cctvPoint, 0, '#');
        moveLeft(cctvPoint, 0, '#');
        moveRight(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveUp(cctvPoint, 0, '#');
        moveLeft(cctvPoint, 0, '#');
        moveDown(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];

        moveUp(cctvPoint, 0, '#');
        moveDown(cctvPoint, 0, '#');
        moveRight(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];
    }
    else if (originalMap[y][x] == 5)
    {
        moveUp(cctvPoint, 0, '#');
        moveDown(cctvPoint, 0, '#');
        moveLeft(cctvPoint, 0, '#');
        moveRight(cctvPoint, 0, '#');
        backtracking(depth + 1);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                originalMap[i][j] = tempMap[i][j];
    }
}

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 >> originalMap[i][j];
            if (1 <= originalMap[i][j] && originalMap[i][j] <= 5)
                cctvPoints.push_back({i, j});
        }
    }

    backtracking(0);

    cout << answer << '\n';

    return 0;
}
      저작자표시 (새창열림)

      '프로그래밍 > 알고리즘 PS' 카테고리의 다른 글

      [C++] BOJ 18242번 - 네모네모 시력검사  (0) 2024.05.24
      [C++] BOJ 1992번 - 쿼드트리  (1) 2024.05.14
      [Python] 프로그래머스 - 오픈채팅방  (0) 2024.05.14
      [C++] BOJ 5430번: AC  (1) 2024.04.19
      [C++] Programmers: 의상  (0) 2024.04.18

      관련글 관련글 더보기

    Designed by Tistory.

    티스토리툴바