처음으로 시뮬레이션 문제를 풀었다.
처음에는 막막했지만 하나하나 생각해본 대로 구현해보는 과정이 재밌기도 했고, 문제를 풀고 난 뒤 다른 풀이를 알아보고 코드를 최적화하는 과정에서 여럿 깨달은 점이 있어 이를 정리해보았다. (여러 삽질 과정도 함께)
문제
https://www.acmicpc.net/problem/15683
15683번: 감시
스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감
www.acmicpc.net
아이디어 - 1
최대 8개까지 존재할 수 있는 cctv는 4가지 방향을 가지기 때문에, 모든 경우의 수를 계산한 후 사각지대의 최솟값을 알아내야 한다.
'모든 경우의 cctv 방향에 대한 계산' 을 구현하는 것이 나에겐 쉽지 않았다.
이에 대해 내가 처음에 사용한 풀이는 8중 for문이었다. 각 for문의 조건 변수를 0부터 3까지 설정하였고, 문제 상에서 주어진 cctv 개수를 이용하여 특정 for문까지 도달했을 경우 조건 변수(cctv의 방향으로 작용)와 cctv 정보를, 감시 공간을 확장시키는 함수로 넘겨주는 방식으로 말이다.
코드 - 1
#include <bits/stdc++.h>
using namespace std;
int n, m;
int board[8][8];
int boardCpy[8][8];
int cannotObs;
int cannotObsCpy;
vector<pair<pair<int, int>, int>> cctv;
vector<int> res;
int dx[4]{1, 0, -1, 0};
int dy[4]{0, 1, 0, -1};
void func1(int x, int y, int dir)
{
x += dx[dir];
y += dy[dir];
while (x >= 0 && x < n && y >= 0 && y < m)
{
if (boardCpy[x][y] == 6)
break;
if (boardCpy[x][y] == 0)
{
cannotObsCpy--;
boardCpy[x][y] = -1;
}
x += dx[dir];
y += dy[dir];
}
}
void func2(int x, int y, int dir)
{
for (int i{0}; i < 4; i++)
{
if (dir % 2 == i % 2)
{
int nx{x}, ny{y};
nx += dx[i];
ny += dy[i];
while (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (boardCpy[nx][ny] == 6)
break;
if (boardCpy[nx][ny] == 0)
{
cannotObsCpy--;
boardCpy[nx][ny] = -1;
}
nx += dx[i];
ny += dy[i];
}
}
}
}
void func3(int x, int y, int dir)
{
int nx{x}, ny{y};
nx += dx[dir];
ny += dy[dir];
while (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (boardCpy[nx][ny] == 6)
break;
if (boardCpy[nx][ny] == 0)
{
cannotObsCpy--;
boardCpy[nx][ny] = -1;
}
nx += dx[dir];
ny += dy[dir];
}
dir = (dir + 1) % 4;
nx = x;
ny = y;
nx += dx[dir];
ny += dy[dir];
while (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (boardCpy[nx][ny] == 6)
break;
if (boardCpy[nx][ny] == 0)
{
cannotObsCpy--;
boardCpy[nx][ny] = -1;
}
nx += dx[dir];
ny += dy[dir];
}
}
void func4(int x, int y, int dir)
{
for (int i{0}; i < 4; i++)
{
if (dir != i)
{
int nx{x}, ny{y};
nx += dx[i];
ny += dy[i];
while (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (boardCpy[nx][ny] == 6)
break;
if (boardCpy[nx][ny] == 0)
{
cannotObsCpy--;
boardCpy[nx][ny] = -1;
}
nx += dx[i];
ny += dy[i];
}
}
}
}
void func5(int x, int y)
{
for (int i{0}; i < 4; i++)
{
int nx{x}, ny{y};
nx += dx[i];
ny += dy[i];
while (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
if (boardCpy[nx][ny] == 6)
break;
if (boardCpy[nx][ny] == 0)
{
cannotObsCpy--;
boardCpy[nx][ny] = -1;
}
nx += dx[i];
ny += dy[i];
}
}
}
void func(pair<pair<int, int>, int> p, int dir)
{
int cctvNum{p.second};
int x{p.first.first}, y{p.first.second};
switch (cctvNum)
{
case 1:
func1(x, y, dir);
break;
case 2:
func2(x, y, dir);
break;
case 3:
func3(x, y, dir);
break;
case 4:
func4(x, y, dir);
break;
case 5:
func5(x, y);
break;
}
}
void copyBoard()
{
for (int i{0}; i < n; i++)
for (int j{0}; j < m; j++)
boardCpy[i][j] = board[i][j];
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i{0}; i < n; i++)
{
for (int j{0}; j < m; j++)
{
cin >> board[i][j];
if (board[i][j] == 0)
cannotObs++;
else if (board[i][j] == 6)
continue;
else
cctv.push_back({{i, j}, board[i][j]});
}
}
int forSize = cctv.size();
for (int a{0}; a < 4; a++)
{
if (forSize == 0)
break;
for (int b{0}; b < 4; b++)
{
if (forSize == 1)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
res.push_back(cannotObsCpy);
break;
}
for (int c{0}; c < 4; c++)
{
if (forSize == 2)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
res.push_back(cannotObsCpy);
break;
}
for (int d{0}; d < 4; d++)
{
if (forSize == 3)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
res.push_back(cannotObsCpy);
break;
}
for (int e{0}; e < 4; e++)
{
if (forSize == 4)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
res.push_back(cannotObsCpy);
break;
}
for (int f{0}; f < 4; f++)
{
if (forSize == 5)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
res.push_back(cannotObsCpy);
break;
}
for (int g{0}; g < 4; g++)
{
if (forSize == 6)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
func(cctv[5], f);
res.push_back(cannotObsCpy);
break;
}
for (int h{0}; h < 4; h++)
{
if (forSize == 7)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
func(cctv[5], f);
func(cctv[6], g);
res.push_back(cannotObsCpy);
break;
}
// forsize == 8
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
func(cctv[5], f);
func(cctv[6], g);
func(cctv[7], h);
res.push_back(cannotObsCpy);
}
}
}
}
}
}
}
}
if (!cctv.empty())
cout << *min_element(res.begin(), res.end());
else
cout << cannotObs;
}이야.. 지금 봐도 상당히 무식한 풀이이다.
결과적으로 맞는 풀이이긴 했으나, 여러 개선 사항을 적용시킬 수 있어 보였다.
아이디어 - 2
1. '모든 경우의 cctv 방향에 대한 계산'은 '백트래킹'으로 구현이 가능하다.
2. func1~func5와 같이, 1~5번 cctv에 대한 각각의 함수를 굳이 구현하지 않아도 된다. 그냥 cctv의 좌표와 방향을 입력받으면 그 방향으로 감시영역을 뻗어나가는 함수를 정의하고, cctv 번호에 따라 이 함수를 방향을 바꿔가며 여러 번 호출하면 된다.
그 외에도 cctv 번호는 좌표로 접근이 가능하므로 굳이 변수로 저장할 필요가 없다던지 등등.. 많은 개선 사항이 있었다.
수정할 사항이 꽤 많고, 또한 백트래킹이 나에게는 익숙하지 않기에 일단은 2번과 그 외의 개선사항 등을 먼저 적용해 보았다.
코드 - 2
// 개선점
// 1. func1 ~ func5 대체.
// 2. cctv에 굳이 cctvNum 안넣도록 대체.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int board[8][8]; // 입력값을 담을 이중배열 선언.
int boardCpy[8][8];
int cannotObs; // 감시할 수 없는 구역의 수(==0의 수) 선언.
int cannotObsCpy;
vector<pair<int, int>> cctv; // cctv의 좌표값을 담을 벡터 선언.
vector<int> res; // 매 경우의 수마다 얻은, 감시할 수 없는 구역의 수를 담을 벡터.
int dx[4]{1, 0, -1, 0};
int dy[4]{0, 1, 0, -1};
void extend(pair<int, int> cctv, int dir)
{
dir %= 4;
int x{cctv.first};
int y{cctv.second};
x += dx[dir];
y += dy[dir];
while (x >= 0 && x < n && y >= 0 && y < m)
{
if (boardCpy[x][y] == 6)
break;
if (boardCpy[x][y] == 0)
{
cannotObsCpy--;
boardCpy[x][y] = -1;
}
x += dx[dir];
y += dy[dir];
}
}
void func(pair<int, int> cctv, int dir)
{ // cctv 정보와 방향 정보 넘겨받음. cctv 번호에 따라 extend 호출 다르게.
int cctvNum{board[cctv.first][cctv.second]};
switch (cctvNum)
{
case 1:
extend(cctv, dir);
break;
case 2:
extend(cctv, dir);
extend(cctv, dir + 2);
break;
case 3:
extend(cctv, dir);
extend(cctv, dir + 1);
break;
case 4:
extend(cctv, dir);
extend(cctv, dir + 1);
extend(cctv, dir + 2);
break;
case 5:
extend(cctv, dir);
extend(cctv, dir + 1);
extend(cctv, dir + 2);
extend(cctv, dir + 3);
break;
}
}
void copyBoard() // 매 경우의 수마다 board값을 직접 변화시킬 수 없기에, 그 복사본을 만드는 함수.
{
for (int i{0}; i < n; i++)
for (int j{0}; j < m; j++)
boardCpy[i][j] = board[i][j];
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i{0}; i < n; i++)
{
for (int j{0}; j < m; j++)
{
cin >> board[i][j];
if (board[i][j] == 0)
cannotObs++;
else if (board[i][j] == 6)
continue;
else
cctv.push_back({i, j});
}
}
int forSize = cctv.size();
for (int a{0}; a < 4; a++)
{
if (forSize == 0)
break;
for (int b{0}; b < 4; b++)
{
if (forSize == 1)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
res.push_back(cannotObsCpy);
break;
}
for (int c{0}; c < 4; c++)
{
if (forSize == 2)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
res.push_back(cannotObsCpy);
break;
}
for (int d{0}; d < 4; d++)
{
if (forSize == 3)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
res.push_back(cannotObsCpy);
break;
}
for (int e{0}; e < 4; e++)
{
if (forSize == 4)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
res.push_back(cannotObsCpy);
break;
}
for (int f{0}; f < 4; f++)
{
if (forSize == 5)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
res.push_back(cannotObsCpy);
break;
}
for (int g{0}; g < 4; g++)
{
if (forSize == 6)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
func(cctv[5], f);
res.push_back(cannotObsCpy);
break;
}
for (int h{0}; h < 4; h++)
{
if (forSize == 7)
{
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
func(cctv[5], f);
func(cctv[6], g);
res.push_back(cannotObsCpy);
break;
}
// forsize == 8
cannotObsCpy = cannotObs;
copyBoard();
func(cctv[0], a);
func(cctv[1], b);
func(cctv[2], c);
func(cctv[3], d);
func(cctv[4], e);
func(cctv[5], f);
func(cctv[6], g);
func(cctv[7], h);
res.push_back(cannotObsCpy);
}
}
}
}
}
}
}
}
if (!cctv.empty()) // 만약 cctv가 1개도 없다면, res는 비어있을 것임.
cout << *min_element(res.begin(), res.end());
else
cout << cannotObs;
}아직도 길기는 하지만, 그래도 어느 정도는 코드의 길이를 줄일 수 있었다.
마지막으로 백트래킹을 이용하여 최종적으로 구현해 보았다.
최종 코드
#include <bits/stdc++.h>
using namespace std;
int n, m;
int board[8][8]; // 입력값을 담을 이중배열 선언.
int cannotObs; // 감시할 수 없는 구역의 수 선언.
vector<pair<int, int>> cctv; // cctv의 좌표값을 담을 벡터 선언.
int dx[4]{1, 0, -1, 0};
int dy[4]{0, 1, 0, -1};
// 상,하,좌,우 특정 방향으로 뻗어나갈 때 이용할 변수.
void extend(pair<int, int> cctv, int dir)
{
dir %= 4;
// dir은 0~3의 범위를 가지므로
// 이보다 큰 값을 가지게 될 경우의 처리.
int x{cctv.first};
int y{cctv.second};
x += dx[dir];
y += dy[dir];
while (x >= 0 && x < n && y >= 0 && y < m)
{
if (board[x][y] == 6)
break;
if (board[x][y] == 0)
board[x][y] = -1;
x += dx[dir];
y += dy[dir];
// 주어진 방향에 따라, 벽을 만나거나 주어진 n*m 범위를 벗어나기 전까지
// 해당 방향으로 뻗어나가며 board값을 변경함.
}
}
void func(pair<int, int> cctv, int dir)
{ // cctv 정보와 방향 정보 넘겨받음. cctv 번호에 따라 extend 호출 다르게.
int cctvNum{board[cctv.first][cctv.second]};
// cctv의 정보와 방향 정보에 따라 extend함수 호출.
switch (cctvNum)
{
case 1:
extend(cctv, dir);
break;
case 2:
extend(cctv, dir);
extend(cctv, dir + 2);
break;
case 3:
extend(cctv, dir);
extend(cctv, dir + 1);
break;
case 4:
extend(cctv, dir);
extend(cctv, dir + 1);
extend(cctv, dir + 2);
break;
case 5:
extend(cctv, dir);
extend(cctv, dir + 1);
extend(cctv, dir + 2);
extend(cctv, dir + 3);
break;
}
}
void back(int idx)
{
if (idx == cctv.size())
{ // 모든 cctv를 확인한 상태.
// 최종적으로 완성된 board를 돌면서 감시되지 않은 구역 수 체크.
int cnt{0};
for (int i{0}; i < n; i++)
for (int j{0}; j < m; j++)
if (board[i][j] == 0)
cnt++;
cnt < cannotObs ? cannotObs = cnt : NULL;
// 확인한 cnt값이 cannotObs보다 작을 경우 cannotObs 값 최신화.
return;
}
int backup[8][8];
for (int i{0}; i < n; i++)
{
for (int j{0}; j < m; j++)
{
backup[i][j] = board[i][j];
}
// extend함수는 board값을 변화시킴.
// 특정 단계에서의 back함수 호출이 끝난 후
// board값을 원래 상태로 되돌려놓기 위한 backUp변수 선언.
}
for (int dir{0}; dir < 4; dir++)
{
func(cctv[idx], dir);
// 현재 단계에서의 idx번째 cctv를 이용한 func함수 호출.
// dir값을 이용해 총 4방향으로 cctv를 돌려 본다.
back(idx + 1);
for (int i{0}; i < n; i++)
{
for (int j{0}; j < m; j++)
{
board[i][j] = backup[i][j];
}
// 다음 단계의 back함수 호출이 끝나면
// 다시 원래대로 board값을 되돌려 놓는다.
}
}
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i{0}; i < n; i++)
{
for (int j{0}; j < m; j++)
{
cin >> board[i][j];
// board값을 입력받고, 이 값에 따라
// cannotObs, cctv 변수 처리.
if (board[i][j] == 0)
cannotObs++;
else if (board[i][j] == 6)
continue;
else
cctv.push_back({i, j});
}
}
back(0);
cout << cannotObs;
}
'알고리즘' 카테고리의 다른 글
| [BOJ] 2504 : 괄호의 값 / C++ (1) | 2023.12.29 |
|---|---|
| [BOJ] 1941 - 소문난 7공주 / C++ (0) | 2022.12.07 |
| [알고리즘] next_permutation - 순열과 조합 / C++ (3) | 2022.12.05 |
| [BOJ] 15649 : N과 M(1) - next_permutation 풀이 / C++ (0) | 2022.12.05 |
| [BOJ] 18870 : 좌표 압축 - map / pair / unique&erase 각각을 활용한 풀이 / C++ (0) | 2022.11.16 |