프로그래밍/알고리즘 PS
[C++] BOJ 15683번 - 감시
코딩 제이티
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;
}