삼성 SW 역량 테스트 기출 문제들을 쭉 풀어보기로 했다.
이번 문제는 백준 골드 4 문제 감시 문제이다.
문제를 한 번 차근차근 읽어보자.
5종류의 CCTV가 있고, 각 CCTV를 회전시켜보는 문제이다.
CCTV를 회전시켜 사각지대가 최소가 되는 경우를 요구하고 있다.
이 때, 사무실의 크기는 최대 8x8이고, CCTV는 6개까지 가능하다.
내가 생각하기엔 직접 모든 경우를 찾아야 될 것 같다.
각 CCTV는 5번을 제외하면 4방향으로 돌릴 수 있는데, 한 번 생각해보자.
CCTV의 위치는 이미 고정되어 있고, 모든 CCTV의 조합을 생각해보면?
4^6 = 4096 가지의 경우가 나온다.
그리고 매 조합 사이사이에 사각지대를 계산하기 위해 이중 for문을 돌리면,
O(N^2)일 때, 최대 N이 8로 그렇게 오랜 시간이 걸리지 않을 것 같다.
한 번 직접 구현을 해보도록 하자.
만약 시간초과가 발생하면, 그 때 가서 고쳐도 된다.
완전 탐색
우선, CCTV의 가시 거리를 표시하기 이전에 방향을 어떻게 설정할까?
각 CCTV 별 방향의 모든 조합을 둘러볼 수 있어야 한다.
CCTV의 수만큼 탐색을 진행하며, 매 탐색마다 CCTV의 방향을 설정할 수 있을까?
먼저, 재귀를 통해서 각 깊이마다 CCTV의 방향을 설정하고자 했다.
배열을 하나 만들어, 각 CCTV의 방향을 정한 뒤 저장해놓는다.
CCTV의 수 만큼의 깊이에 도달했을 때 해당 방향 조합을 한 번에 이용할 수 있다.
void backtrack(int depth, int direction) {
if (depth == cctv_list.size()) {
copy_office();
for (int i = 0; i < cctv_list.size(); i++)
draw_range(cctv_list[i], direction_list[i]);
answer = min(answer, calculate_blind_spot());
return;
}
for (int i = 0; i < 4; i++) {
// 각 깊이 별로 선택되는 방향을 의미한다.
direction_list.push_back(i);
backtrack(depth + 1, i);
direction_list.pop_back();
}
}
for (int i = 0; i < 4; i++) {
direction_list.push_back(i);
backtrack(1, i);
direction_list.pop_back();
}위의 코드대로 구현했으며, 이는 Backtracking 방식을 사용한다.
흔히 순열, 조합을 뽑을 때 백트래킹을 사용하는데, 동일한 방식이다.
그럼, 해당 방향 조합대로 가시 범위는 어떻게 표시할까?
이 방식 또한 재귀를 사용해서 일자로 쭉 깊이 파고들도록 해보자.
void draw(int x, int y, int direction){
if ((x >= 0 && x < row) && (y >= 0 && y < col)) {
if (office[x][y] != 6) {
if (office[x][y] == 0)
copied_office[x][y] = -9; // 가시 범위
draw(x + dx[direction], y + dy[direction], direction);
}
}
}
void draw_range(pair<int, int>& start_pos, int direction) {
int kind_of_cctv = office[start_pos.first][start_pos.second];
// 현재 어떤 종류의 CCTV를 보고있는지?
if (kind_of_cctv == 1) {
draw(start_pos.first + dx[direction], start_pos.second + dy[direction], direction);
}
if (kind_of_cctv == 2) {
draw(start_pos.first + dx[direction], start_pos.second + dy[direction], direction);
draw(start_pos.first + dx[(direction + 2) % 4], start_pos.second + dy[(direction + 2) % 4], ((direction + 2) % 4));
}
if (kind_of_cctv == 3) {
for(int i = 0; i < 2; i++)
draw(start_pos.first + dx[(direction + i) % 4], start_pos.second + dy[(direction + i) % 4], (direction + i) % 4);
}
if (kind_of_cctv == 4) {
for (int i = 0; i < 3; i++)
draw(start_pos.first + dx[(direction + i) % 4], start_pos.second + dy[(direction + i) % 4], (direction + i) % 4);
}
if (kind_of_cctv == 5) {
for (int i = 0; i < 4; i++)
draw(start_pos.first + dx[(direction + i) % 4], start_pos.second + dy[(direction + i) % 4], (direction + i) % 4);
}
}위 코드와 같이 구현했다.
위 함수로 매번 가시 범위를 그린 다음, 사각지대를 계산하도록 했다.
하지만 곧바로 메모리 초과가 발생했다.
시간 초과가 아닌 메모리 초과가 뜬다? 이 부분은 조금 이해가 안됐다.
아마 재귀 방식이 stack 메모리를 사용하기 때문에 발생한 것 같은데,
특정 예제에서 재귀를 너무 많이 돈다는 말이 된다.
잠시 반례에 대해 생각을 조금 해보니, edge case를 하나 빼먹었다.
CCTV가 아예 없을 때 내 코드는 무한히 재귀를 들어가게 된다.
if (depth >= cctv_list.size())그래서, 재귀 중지 조건을 CCTV를 모두 탐색했을 때가 아닌,
깊이가 CCTV의 갯수보다 많아졌을 때로 고쳤다.
이렇게 되면 CCTV가 없을 때 바로 함수를 종료하게 된다.
결국 해냈다!
삼성 SW 역량 문제를 차근차근 풀다보니 어지러운 구현 문제가 좀 많은 것 같다.
시간 복잡도를 반드시 고민하며 풀어야 할 문제들인 것 같고,
최대한 시간을 줄이려는 아이디어도 필요할 것 같다.