Memo
•
방향을 이렇게 많이 고려해야 하는 문제는 이 문제가 처음이었습니다.
•
cctv마다 방향을 다르게 해서 브루트 포스를 돌립니다.
•
번호에 따라 방향이 다르기 때문에 실수를 하게 됐습니다. 좀 더 신중히 확인하며 작성해야겠다 생각이 들었습니다.
Code
제출 날짜
@3/30/2021
메모리
2016 KB
시간
8 ms
#include <iostream>
#include <vector>
#include <algorithm>
int N, M;
int g_map[10][10];
int one_y[4] = {0, 1, 0, -1};
int one_x[4] = {1, 0, -1, 0};
int two_y[2][2] = {{0, 0}, {1, -1}};
int two_x[2][2] = {{1, -1}, {0, 0}};
int three_y[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int three_x[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int four_y[4][3] = {{0, -1, 0}, {-1, 0, 1}, {0, 1, 0}, {1, 0, -1}};
int four_x[4][3] = {{-1, 0, 1}, {0, 1, 0}, {1, 0, -1}, {0, -1, 0}};
int five_y[1][4] = {{0, -1, 0, 1}};
int five_x[1][4] = {{1, 0, -1, 0}};
std::vector<std::pair<int, int> >cctv;
int ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N >> M;
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < M ; j++)
{
std::cin >> g_map[i][j];
if (g_map[i][j] >= 1 && g_map[i][j] <= 5)
cctv.push_back({i, j});
}
ans = 9999;
}
void shoot_operation(int y, int x, int dy, int dx, int ind)
{
int nx, ny;
nx = x + dx;
ny = y + dy;
if (nx < 0 || nx >= M || ny < 0 || ny >= N || g_map[ny][nx] == 6)
return ;
if (g_map[ny][nx])
shoot_operation(ny, nx, dy, dx, ind);
else
{
g_map[ny][nx] = ind;
shoot_operation(ny, nx, dy, dx, ind);
}
}
void shoot_back_operation(int y, int x, int dy, int dx, int ind)
{
int nx, ny;
nx = x + dx;
ny = y + dy;
if (nx < 0 || nx >= M || ny < 0 || ny >= N)
return ;
if (g_map[ny][nx] == ind)
g_map[ny][nx] = 0;
shoot_back_operation(ny, nx, dy, dx, ind);
}
void cal_blind_spot()
{
int cnt = 0;
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < M ; j++)
if (!g_map[i][j])
cnt++;
ans = std::min(ans, cnt);
}
void brute_force(int ind)
{
int y = cctv[ind].first;
int x = cctv[ind].second;
int g_map_val = g_map[y][x];
if (ind == cctv.size())
{
cal_blind_spot();
return ;
}
if (g_map_val == 1)
{
for (int i = 0 ; i < 4 ; i++)
{
shoot_operation(y, x, one_y[i], one_x[i], 10 + ind);
brute_force(ind + 1);
shoot_back_operation(y, x, one_y[i], one_x[i], 10 + ind);
}
}
else if (g_map_val == 2)
{
for (int i = 0 ; i < 2 ; i++)
{
for (int j = 0 ; j < 2 ; j++)
shoot_operation(y, x, two_y[i][j], two_x[i][j], 10 + ind);
brute_force(ind + 1);
for (int j = 0 ; j < 2 ; j++)
shoot_back_operation(y, x, two_y[i][j], two_x[i][j], 10 + ind);
}
}
else if (g_map_val == 3)
{
for (int i = 0 ; i < 4 ; i++)
{
for (int j = 0; j < 2 ; j++)
shoot_operation(y, x, three_y[i][j], three_x[i][j], 10 + ind);
brute_force(ind + 1);
for (int j = 0 ; j < 2 ; j++)
shoot_back_operation(y, x, three_y[i][j], three_x[i][j], 10 + ind);
}
}
else if (g_map_val == 4)
{
for (int i = 0 ; i < 4 ; i++)
{
for (int j = 0 ; j < 3 ; j++)
shoot_operation(y, x, four_y[i][j], four_x[i][j], 10 + ind);
brute_force(ind + 1);
for (int j = 0 ; j < 3; j++)
shoot_back_operation(y, x, four_y[i][j], four_x[i][j], 10 + ind);
}
}
else if (g_map_val == 5)
{
for (int i = 0 ; i < 4 ; i++)
shoot_operation(y, x, five_y[0][i], five_x[0][i], 10 + ind);
brute_force(ind + 1);
for (int i = 0 ; i < 4 ; i++)
shoot_back_operation(y, x, five_y[0][i] , five_x[0][i], 10 + ind);
}
}
void solve()
{
if (!cctv.size())
{
cal_blind_spot();
return ;
}
brute_force(0);
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
