알고리즘을 공부하다가 나온 첫 구현문제라 삽질을 좀 오래했다..
처음 알게 된 개념도 있고 해서 이것저것 정리를 하려고 한다.
정해진 크기의 방안에 서로 볼 수 있는 영역이 다른 CCTV들이 들어 있는데 이 CCTV들을 어떻게 배치하면 사각지대를 최소한으로 만들 수 있을까?
가장 처음으로 시도한 코드는 다음과 같다.
첫 시도 (17%에서 fail + 300줄 흐름만 보고 넘어가자)
첫 시도에서의 아이디어는 다음과 같다.
int x_pos_plus(int i, int j, int cctv)
{
int cnt = 0;
for (int k = j; k < m; k++)
{
if (room[i][k] == 6)
break;
if (vis[i][k] == 0)
{
vis[i][k] = cctv;
cnt++;
}
}
return cnt;
}
int x_pos_minus(int i, int j, int cctv)
{
int cnt = 0;
for (int k = j; k >= 0; k--)
{
if (room[i][k] == 6)
break;
if (vis[i][k] == 0)
{
vis[i][k] = cctv;
cnt++;
}
}
return cnt;
}
int y_pos_plus(int i, int j, int cctv)
{
int cnt = 0;
for (int k = i; k < n; k++)
{
if (room[k][j] == 6)
break;
if (vis[k][j] == 0)
{
vis[k][j] = cctv;
cnt++;
}
}
return cnt;
}
int y_pos_minus(int i, int j, int cctv)
{
int cnt = 0;
for (int k = i; k >= 0; k--)
{
if (room[k][j] == 6)
break;
if (vis[k][j] == 0)
{
vis[k][j] = cctv;
cnt++;
}
}
return cnt;
}모든 cctv는 어떤 방향이든 직선으로 감시한다.
감시한 공간에 표시를 남기고, 몇개의 공간을 감시했는지 반환해주는 함수를 만들었다.
이걸 cctv1, 2, 3, 4, 5 모두에 적용했더니
회전과는 상관 없이 모든 방향을 감시하는 cctv5를 제외하고 cctv마다 if문이 4개씩 필요했다.
또한 많은 구역을 검사하는 cctv5 ~ cctv1 순으로 검사를 진행하다 보니 몇개의 cctv가 상호작용해서 더 많은 구역을 검사할 수 있는 반례를 만족하지 못했다.
그래도 배운것들이 좀 있다.
저 어마무시한 코드들을 좀 줄여보고자 여기저기 돌아다닌 끝에
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// dir(direction)변수는 방위(0:동, 1:서, 2:남, 3:북)을 가리킴
int go_edge(int i, int j, int cctv, int dir)
{
int cnt = 0;
for (int k = 0; true; k++)
{
int nx = k * dx[dir] + i;
int ny = k * dy[dir] + j;
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (room[nx][ny] == 6)
break;
if (vis[nx][ny] == 0)
{
vis[nx][ny] = cctv;
cnt++;
}
}
return cnt;
}위에서 본 4개 함수를 하나로 합쳐서, 요런 아름다운 코드를 완성했다. 생각해보니 BFS랑 비슷한데 왜 생각 못했을까..
이런 생각이 들때 쯤 아예 접근이 틀려먹었단 생각이 들어서 코드를 전부 갈아 엎었다. (사실 바킹독님의 해설을 봤다)
// 감시
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m;
int board1[10][10]; // board입력
int board2[10][10]; // board복사용
vector<pair<int, int>> cctv;
bool OOB(int a, int b) // 범위 확인(Out Of Bound방지)
{
return a < 0 || a >= n || b < 0 || b >= m;
}
void upd(int x, int y, int dir) // 직선으로 진행하면서 감시된 구역을 7로 바꿈
{
dir %= 4; // 방향 지정(4진수 표현)
while (1)
{
x += dx[dir];
y += dy[dir];
if (OOB(x, y) || board2[x][y] == 6)
return;
if (board2[x][y] != 0)
continue;
board2[x][y] = 7;
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int mn = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> board1[i][j];
if (board1[i][j] != 0 && board1[i][j] != 6)
cctv.push_back({i, j});
if (board1[i][j] == 0)
mn++;
}
}
for (int tmp = 0; tmp < (1 << (2 * cctv.size())); tmp++)
{ // cctv의 갯수가 k개 일때 4^k만큼 반복
// 즉 tmp를 4진법으로 생각하고 각 자리수가 cctv의 방향이 됨.
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
board2[i][j] = board1[i][j]; // 테스트용 보드 생성
int brute = tmp;
for (int i = 0; i < (int)cctv.size(); i++)
{ // board 안의 모든 cctv가 감시가능한 구역 설정
int dir = brute % 4;
brute /= 4;
int x = cctv[i].X
int y = cctv[i].Y
if (board1[x][y] == 1)
upd(x, y, dir);
else if (board1[x][y] == 2)
{
upd(x, y, dir);
upd(x, y, dir + 2);
}
else if (board1[x][y] == 3)
{
upd(x, y, dir);
upd(x, y, dir + 1);
}
else if (board1[x][y] == 4)
{
upd(x, y, dir);
upd(x, y, dir + 1);
upd(x, y, dir + 2);
}
else
{
upd(x, y, dir);
upd(x, y, dir + 1);
upd(x, y, dir + 2);
upd(x, y, dir + 3);
}
}
int val = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
val += (board2[i][j] == 0);
mn = min(mn, val);
}
cout << mn;
}가능한 방향의 종류가 4개 이므로 4진법을 사용한다.
0,1,2,3으로 표현되므로 각각 동, 북, 서, 남을 뜻한다.
"감시한다" 를 코드로 표현한 upd함수를 보면
void upd(int x, int y, int dir) // 직선으로 진행하면서 감시된 구역을 7로 바꿈
{
dir %= 4; // 방향 지정(4진수 표현)
while (1)
{
x += dx[dir];
y += dy[dir];
if (OOB(x, y) || board2[x][y] == 6)
return;
if (board2[x][y] != 0)
continue;
board2[x][y] = 7;
}
}위와 같은데 방향을 처음부터 지정해 값을 계속 더하며(즉, 전진하며) 감시를 계속 한다.
이 코드는 내가 위에서 짰던
int go_edge(int i, int j, int cctv, int dir)
{
int cnt = 0;
for (int k = 0; true; k++)
{
int nx = k * dx[dir] + i;
int ny = k * dy[dir] + j;
if (nx < 0 || nx >= m || ny < 0 || ny >= n)
break;
if (room[nx][ny] == 6)
break;
if (vis[nx][ny] == 0)
{
vis[nx][ny] = cctv;
cnt++;
}
}
return cnt;
}
이 코드와 굉장히 흡사하고 기능도 거의 같다.
차이점은 감시한 공간의 갯수 반환 유무이다.
그렇다면 나는 어디서 틀린 것일까?
바로 감시할 수 있는 모든 경우의 수를 확인하지 않았던 것이다!
해설에서는 모든 경우의 수를 돌면서 최소값을 찾아냈지만 내 코드는 cctv5부터 cctv1로 내려오면서 가장 많이 볼 수 있는 위치만을 지정했더니 여러개의 cctv가 상호작용해 각각 생각한 것보다 더 많이 볼 수 있는 경우를 찾지 못한 것이다.
따라서 내 코드를 수정해보자면
// 감시
#include <bits/stdc++.h>
using namespace std;
int room[10][10];
int vis[10][10];
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
int n, m, mini = 0;
void go_edge(int i, int j, int dir);
int ch_empty();
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
vector<pair<int, int>> cctv;
cin >> n >> m;
/* 방, 벽, CCTV 위치 초기화 */
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> room[i][j];
if (room[i][j] != 0 && room[i][j] != 6)
cctv.push_back({i, j});
if (room[i][j] == 0)
mini++;
}
}
for (int tmp = 0; tmp < (1 << (2 * cctv.size())); tmp++)
{
copy(&room[0][0], &room[0][0] + 100, &vis[0][0]);
int brute = tmp;
for (int i = 0; i < (int)cctv.size(); i++)
{
int dir = brute % 4;
brute /= 4;
int x, y;
tie(x, y) = cctv[i];
if (room[x][y] == 1)
go_edge(x, y, dir);
else if (room[x][y] == 2)
{
go_edge(x, y, dir);
go_edge(x, y, dir + 2);
}
else if (room[x][y] == 3)
{
go_edge(x, y, dir);
go_edge(x, y, dir + 1);
}
else if (room[x][y] == 4)
{
go_edge(x, y, dir);
go_edge(x, y, dir + 1);
go_edge(x, y, dir + 2);
}
else
{
go_edge(x, y, dir);
go_edge(x, y, dir + 1);
go_edge(x, y, dir + 2);
go_edge(x, y, dir + 3);
}
}
int m = ch_empty();
mini = min(mini, m);
}
cout << mini;
}
// dir(direction)변수는 방위(0:동, 1:서, 2:남, 3:북)을 가리킴
void go_edge(int i, int j, int dir)
{
dir %= 4;
for (int k = 1; true; k++)
{
int nx = k * dx[dir] + i;
int ny = k * dy[dir] + j;
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
return;
if (room[nx][ny] == 6)
return;
if (vis[nx][ny] == 0)
vis[nx][ny] = 7;
}
}
int ch_empty()
{
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
if (vis[i][j] == 0)
ans++;
}
return ans;
}위와 같다..!!!!!
Back-End Developer