풀이 소요시간 : 60분 초과
이런 타입의 백트래킹 문제를 풀이해본 적이 없어서 다소 지저분하게 문제를 풀다가 깔끔하게 정석 풀이를 참고하기로 마음먹었다. 역시나 나의 풀이 방향은 정석과는 거리가 멀었다.
우선 감시 카메라의 정보를 Vector 에 저장했다. 나는 이후 5가지 타입의 카메라의 방향 배열을 모두 선언하는 노가다를 진행했지만, 정석 풀이로는 한 쌍의 방향 배열만 있어도 충분했다.
void Solve(int Count) {
if (Count == Vector.size())
{
int curr = Make_Ans();
Ans = min(Ans, curr);
return;
}
//카메라를 하나하나 짚어봄
int px = Vector[Count].x;
int py = Vector[Count].y;
int pnum = Vector[Count].num;
int Temp[9][9];
for (int d = 0; d < 4; d++)
{
//변화 이전의 Map 상태를 기억하는 Temp 배열 선언
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
Temp[i][j] = Map[i][j];
if (pnum == 1)
{
Search(px, py, d);
}
else if (pnum == 2)
{
Search(px, py, d);
Search(px, py, d + 2);
}
else if (pnum == 3)
{
Search(px, py, d);
Search(px, py, d + 1);
}
else if (pnum == 4)
{
Search(px, py, d);
Search(px, py, d + 1);
Search(px, py, d + 2);
}
else if (pnum == 5)
{
Search(px, py, d);
Search(px, py, d + 1);
Search(px, py, d + 2);
Search(px, py, d + 3);
}
Solve(Count + 1);
//복귀 후 Map 이전상태로 되돌리기
for (int i = 0; i <= N; i++)
for (int j = 0; j <= M; j++)
Map[i][j] = Temp[i][j];
}
}그 이유는 위의 Solve 함수에서 찾아볼 수 있다. 중복이 되어도 상관없으니 d 변수를 이용하여 모든 방향을 탐색하고, 그 과정에 있어서 Search 함수를 구현해 감시카메라의 작동을 반영할 수 있었다.
백트래킹에서 배열의 상태를 저장하는 방법
위의 함수에서는 Temp 라는 배열을 선언했다. 선언 직후 현재 Map 의 상태를 저장하고, 재귀함수 호출에서 돌아온 이후 Map 에 다시 Temp 값을 대입하는 방식을 사용할 수 있었다. 이 방식은 비슷한 문제에서 활용할 수 있을 것 같다. 실제로 문제를 풀면서 배열의 상태를 어떤식으로 저장하고 복구해야하는지 고민했다.
Search 함수의 구현
밑의 전체코드를 보면 알 수 있지만, 굳이 재귀함수를 사용하지 않고 while 문을 통해서 x 와 y 값을 nx 와 ny 로 갱신해가며 탐색을 진행하는 방식도 있다. 이것도 다음에 활용할수 있도록 하자.
전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
int Map[9][9];
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { 1, 0, -1, 0 };
struct Cam {
int x;
int y;
int num;
};
int Ans = 99999;
vector<Cam> Vector;
void Input() {
cin >> N >> M;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
cin >> Map[i][j];
if (Map[i][j] > 0 && Map[i][j] < 6)
{
Vector.push_back({ i, j, Map[i][j]});
}
}
}
}
//사각지대의 넓이
int Make_Ans() {
int Cnt = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
if (Map[i][j] == 0) Cnt++;
}
}
return Cnt;
}
void Search(int x, int y, int num) {
int Dir = num % 4;
while (true)
{
int nx = x + dx[Dir];
int ny = y + dy[Dir];
x = nx;
y = ny;
if (nx < 1 || ny < 1 || nx > N || ny > M) return; //범위 초과
if (Map[nx][ny] == 6) return; //벽
if (Map[nx][ny] != 0) continue; //다른 감시 카메라
Map[nx][ny] = -1;
}
}
void Solve(int Count) {
if (Count == Vector.size())
{
int curr = Make_Ans();
Ans = min(Ans, curr);
return;
}
//카메라를 하나하나 짚어봄
int px = Vector[Count].x;
int py = Vector[Count].y;
int pnum = Vector[Count].num;
int Temp[9][9];
for (int d = 0; d < 4; d++)
{
//변화 이전의 Map 상태를 기억하는 Temp 배열 선언
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
Temp[i][j] = Map[i][j];
if (pnum == 1)
{
Search(px, py, d);
}
else if (pnum == 2)
{
Search(px, py, d);
Search(px, py, d + 2);
}
else if (pnum == 3)
{
Search(px, py, d);
Search(px, py, d + 1);
}
else if (pnum == 4)
{
Search(px, py, d);
Search(px, py, d + 1);
Search(px, py, d + 2);
}
else if (pnum == 5)
{
Search(px, py, d);
Search(px, py, d + 1);
Search(px, py, d + 2);
Search(px, py, d + 3);
}
Solve(Count + 1);
//복귀 후 Map 이전상태로 되돌리기
for (int i = 0; i <= N; i++)
for (int j = 0; j <= M; j++)
Map[i][j] = Temp[i][j];
}
}
int main() {
Input();
Solve(0);
cout << Ans << '\n';
}
SSAFY 11th