삼성 SW 역량테스트 기출문제인 백준 15683번 감시 문제를 풀이해보겠습니다. 어떤 문제든 다양한 풀이법이 존재하니 어떤 식으로 문제를 접근하는지에 집중해야 합니다. 저는 이 감시 기출문제를 조합 문제로 풀이해봤습니다. DFS나 전체 탐색으로 풀이하는 방법도 존재합니다.
2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14888번] 연산자 끼워넣기 (순열)
2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 15686번] 치킨배달 (조합)
2021.04.14 - [알고리즘/SW역량테스트 기출문제] - [백준 14889번] 스타트와 링크 (조합)
2021.04.18 - [알고리즘/SW역량테스트 기출문제] - [백준 15683번] 감시 (조합)
2021.04.20 - [알고리즘/SW역량테스트 기출문제] - [백준 14501번] 퇴사 (조합)
안녕하세요. 지칸입니다.
오늘은 백준 15683번 감시 문제를 풀어보겠습니다. 이 문제뿐만 아니라 기출문제를 여러 사람들이 풀이한 것을 보면 문제 유형을 정의하는 게 제각각입니다. 어떤 방식으로든 풀이할 수 있으니 문제를 해석하는 방법에 집중해주세요.
1) 문제 이해
2) 문제 풀이
저의 결론) 단순한 조합 문제가 아닌 여러 조합이 동시에 사용되는 문제입니다. 문제를 해석하다 보면 이런 식으로 경우의 수를 따져봐야 하는 문제들이 종종 있습니다. 더 간단한 접근으로 전체 탐색을 시도해 볼 수도 있습니다. 저는 조합 템플릿을 재활용하기 위해 조합으로 시도해봤습니다.
1) 문제 이해
문제 출처 : www.acmicpc.net/problem/15683
문제)
스타트 링크의 사무실은 1 ×1 크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.
1번 CCTV는 한쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.
CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.
CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0 |
지도에서 0은 빈칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 # 6 0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 0 0 0 0 0 # # 1 0 6 0 0 0 0 0 0 0 |
0 0 # 0 0 0 0 0 # 0 0 0 0 0 1 0 6 0 0 0 0 0 0 0 |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 6 0 0 0 # 0 0 0 |
| → | ← | ↑ | ↓ |
CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 칸을 감시할 수 없다.
위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각지대의 최소 크기를 구하는 프로그램을 작성하시오.
(나머지 예시는 문제 출처에서 확인해주세요~)
-> 문제 해석
- 5종류의 CCTV
- 각 CCTV의 감시 방향 경우의 수 -> (4, 2, 4, 4, 1)
- 벽은 통과할 수 없지만 CCTV는 통과 가능 -> 해당 방향으로 쭉 전진하며 검사, 벽을 만나거나 맵 범위 벗어나면 종료
- 4개의 방향이 존재, 각 CCTV의 방향도 이 4개 방향의 조합임
- 사각지대의 최소 크기, 최대 크기는 초기 맵의 빈칸-> sol 디폴트 값
- 맵에 CCTV가 주어지면 각 CCTV마다 경우의 수를 발생
- 예를 들어, CCTV2 CCTV1 CCTV3-> 2C1 x 4C1 x 4C1의 경우의 수 발생
입력)
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
-> 입력 해석
- 2차원 맵, MAX_N = 8
- CCTV는 최대 8개, CCTV 배열 8개 생성
출력)
첫째 줄에 사각지대의 최소 크기를 출력한다.
-> 출력 해석
- 모든 경우의 수에서 최소 크기를 비교하며 저장
2) 문제 풀이
이 문제 역시 기본 세팅 먼저 수행합니다.
2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비
2-1) 초기 세팅
input을 수신하는 코드를 구현합니다. 우리는 CCTV 구조체를 만들어서 CCTV의 좌표와 번호를 저장합니다. 최대 8개까지 입력에서 제한했으니 크기 8의 배열로 생성해도 괜찮지만 항상 했던 것처럼 저는 vector로 정의하겠습니다.
#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 8
#define MAX_CCTV 8
#define EMPTY 0
#define CCTV1 1
#define CCTV2 2
#define CCTV3 3
#define CCTV4 4
#define CCTV5 5
#define WALL 6
#define CHECK 7 //#
struct CCTV
{
int y;
int x;
int category; //cctv number
};
enum CCTVdir
{
Right, //cctv1 0
Down,
Left,
Up,
LeftRight, //cctv2 4
UpDown,
UpRight, //cctv3 6
RightDown,
DownLeft,
LeftUp,
LeftUpRight, //cctv4 10
UpRightDown,
RightDownLeft,
DownLeftUp,
LeftUpRightDown //cctv5 14
};
int N, M;
int sol;
int map[MAX_N][MAX_N] = { 0, };
vector<CCTV> cctv;
int main() {
cin >> N >> M;
int temp;
CCTV tempTV;
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> temp;
map[i][j] = temp;
if (map[i][j] == EMPTY) count++;
if (CCTV1 <= temp && temp <= CCTV5) {
tempTV.y = i;
tempTV.x = j;
tempTV.category = temp;
cctv.push_back(tempTV); // add cctv info
}
}
}
sol = count; // set default
//조합 함수 구현
cout << sol;
return 0;
}CCTVdir enum을 보면 알겠지만 매우 지저분하죠... 더 간단하게 숫자를 이용해서 간략한 코딩을 하는 것도 방법이지만 생각이 안 떠오를 때는 이처럼 노가다성으로 풀이해도 괜찮습니다. 무엇을 의미하는지 한눈에 들어옵니다.
2차원 맵을 돌면서 빈칸의 수를 카운팅 하여 sol 변수에 최댓값으로 초기 세팅해줍니다. 그리고 CCTV가 입력될 경우 해당 좌표와 번호를 저장해주세요.
2-2) 조합 구현하기
2021.04.01 - [알고리즘/SW역량테스트] - (4장-2) 조합(Combination) 알고리즘이란?
위 포스팅에서와 다른 점이 있습니다. 위 조합은 단 하나의 조합이었다면 이번 문제는 nCr x nCr 등 조합을 최대 8개까지 곱한 경우의 수를 체크해야 합니다. 그래서 조합 알고리즘 하면 필요한 arr, flag 배열이 2차원으로 확장되었습니다. 각 행 인덱스에 CCTV 인덱스가 들어가고 열 인덱스에 해당 CCTV의 후보를 넣어줍니다.
vector<CCTVdir> arr[MAX_CCTV];
vector<int> flag[MAX_CCTV];
int main() {
cin >> N >> M;
int temp;
CCTV tempTV;
int count = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> temp;
map[i][j] = temp;
if (map[i][j] == EMPTY) count++;
if (CCTV1 <= temp && temp <= CCTV5) {
if (temp == CCTV1) {
for (int k = Right; k <= Up; k++) {
arr[cctv.size()].push_back((CCTVdir)k);
flag[cctv.size()].push_back(0);
}
}
else if (temp == CCTV2) {
for (int k = LeftRight; k <= UpDown; k++) {
arr[cctv.size()].push_back((CCTVdir)k);
flag[cctv.size()].push_back(0);
}
}
else if (temp == CCTV3) {
for (int k = UpRight; k <= LeftUp; k++) {
arr[cctv.size()].push_back((CCTVdir)k);
flag[cctv.size()].push_back(0);
}
}
else if (temp == CCTV4) {
for (int k = LeftUpRight; k <= DownLeftUp; k++) {
arr[cctv.size()].push_back((CCTVdir)k);
flag[cctv.size()].push_back(0);
}
}
else {
arr[cctv.size()].push_back(LeftUpRightDown);
flag[cctv.size()].push_back(0);
}
tempTV.y = i;
tempTV.x = j;
tempTV.category = temp;
cctv.push_back(tempTV);
}
}
}
sol = count;
comb(arr[0].size(), 1, 0);
cout << sol;
return 0;
}간단하게 CCTV2를 예로 들면, LeftRight와 UpDown 두 개를 arr[cctv index][0], arr[cctv index][1]에 넣어주는 동작입니다. 이것으로 comb 함수에 사용될 변수 세팅이 끝났습니다. 맨 처음 호출은 0th cctv의 nC1를 호출하는 것으로 시작합니다.
구체적인 comb함수를 살펴보면 아래와 같습니다. 기존 함수와 큰 차이는 없습니다. arr와 flag가 확장됐다는 것, selectCCTVdir는 1차원 배열 그대로 사용한 점(r이 항상 1이기 때문에), clear가 아닌 pop_back를 사용했다는 점 정도 차이가 있고 나머지는 같습니다. cctvnum 변수를 통해 우리는 몇 번째 CCTV를 선택하고 있는지 알 수 있습니다.
int emptycount = 0;
vector<CCTVdir> selectCCTVdir;
int copymap[MAX_N][MAX_N] = { 0, };
void operation(int cctvnum) {
if (cctvnum + 1 == cctv.size()) {
//for (int i = 0; i < selectCCTVdir.size(); i++) {
// cout << i << "-th cctv, dir : " << selectCCTVdir[i] << endl;
//}
emptycount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
copymap[i][j] = map[i][j];
if (map[i][j] == EMPTY)
emptycount++;
}
}
monitor();
return;
}
comb(arr[cctvnum + 1].size(), 1, cctvnum + 1);
}
void comb(int n, int r, int cctvnum) {
if (n == r) {
for (int i = 0; i < n; i++) {
flag[cctvnum][i] = 1;
}
for (int i = 0; i < arr[cctvnum].size(); i++) {
if (flag[cctvnum][i] == 1) selectCCTVdir.push_back(arr[cctvnum][i]);
}
operation(cctvnum);
selectCCTVdir.pop_back();
for (int i = 0; i < n; i++) {
flag[cctvnum][i] = 0;
}
return;
}
if (r == 1) {
for (int i = 0; i < n; i++) {
flag[cctvnum][i] = 1;
for (int j = 0; j < arr[cctvnum].size(); j++) {
if (flag[cctvnum][j] == 1) selectCCTVdir.push_back(arr[cctvnum][j]);
}
operation(cctvnum);
selectCCTVdir.pop_back();
flag[cctvnum][i] = 0;
}
return;
}
flag[cctvnum][n - 1] = 1;
comb(n - 1, r - 1, cctvnum);
flag[cctvnum][n - 1] = 0;
comb(n - 1, r, cctvnum);
}operation 함수를 보면 기존 조합 알고리즘과 다르게 내부에서 다시 comb를 호출하고 있습니다. 이때 cctvnum를 1 증가시켜 다음 cctv의 조합으로 넘어갑니다. 문제에서 주어진 CCTV 수만큼 들어갈 경우에만 if 조건문에 걸려서 이 문제의 핵심 프로세스가 진행됩니다.
2-3) 감시 영역 체크하기
이 문제도 수많은 경우마다 맵을 썼다 지웠다 반복하기 때문에 copymap를 생성합니다. 이때 빈칸을 미리 카운트합니다. 그리고 monitor 함수를 통해 감시 영역을 체크하도록 합니다.
int dy[4] = { 0,1,0,-1 }; //R, D, L, U
int dx[4] = { 1,0,-1,0 };
bool checkmaprange(int y, int x) {
if ((0 <= y && y < N) && (0 <= x && x < M))
return true;
return false;
}
void check(int cctvindex, CCTVdir dir) {
int y = cctv[cctvindex].y;
int x = cctv[cctvindex].x;
while (copymap[y][x] != WALL && checkmaprange(y, x)) {
if (copymap[y][x] == EMPTY) {
copymap[y][x] = CHECK;
emptycount--;
}
y += dy[dir];
x += dx[dir];
}
}
void monitor() {
int category;
CCTVdir dir;
for (int i = 0; i < selectCCTVdir.size(); i++) {
category = cctv[i].category;
dir = selectCCTVdir[i];
if (category == CCTV1) {
check(i, dir);
}
else if (category == CCTV2) {
if (dir == LeftRight) {
check(i, Left);
check(i, Right);
}
else { //UpDown
check(i, Up);
check(i, Down);
}
}
else if (category == CCTV3) {
if (dir == UpRight) {
check(i, Up);
check(i, Right);
}
else if (dir == RightDown) {
check(i, Right);
check(i, Down);
}
else if (dir == DownLeft) {
check(i, Down);
check(i, Left);
}
else if (dir == LeftUp) {
check(i, Left);
check(i, Up);
}
}
else if (category == CCTV4) {
if (dir == LeftUpRight) {
check(i, Left);
check(i, Up);
check(i, Right);
}
else if (dir == UpRightDown) {
check(i, Up);
check(i, Right);
check(i, Down);
}
else if (dir == RightDownLeft) {
check(i, Right);
check(i, Down);
check(i, Left);
}
else if (dir == DownLeftUp) {
check(i, Down);
check(i, Left);
check(i, Up);
}
}
else {
check(i, Right);
check(i, Down);
check(i, Left);
check(i, Up);
}
}
if (sol > emptycount)
sol = emptycount;
}감시영역을 체크하는 프로세스 순서는 아래와 같습니다.
- 입력으로 주어진 CCTV의 수만큼 반복하면서 CCTV번호를 확인합니다.
- 조합을 통해 각 CCTV마다 이번 경우의 방향이 정해져 있습니다.
- CCTV마다 방향을 동서남북 4개의 방향으로 분해하여 check함수를 호출합니다.
- 예를 들어, RighDownLeft 방향이면 check의 파라미터로 Righ, Down, Left 3번 넣어서 호출합니다.
- check 함수에서 CCTV의 좌표, 한 방향에 대해 감시영역을 맵에 표기합니다.
- 맵에 표기하면서 빈칸을 감소시킬 때마다 emptycount-- 합니다.
- 벽을 만나거나 맵 범위를 벗어나면 check함수는 종료됩니다.
- 모든 CCTV에 대해 반복 후 남은 사각지대와 기존 최솟값 sol를 비교하여 업데이트합니다.
if-else가 많아서 상당히 복잡해 보일 수 있고 성능에 악영향이 있을 수 있습니다. 하지만 문제의 변수 크기를 보면 이 정도의 if문으로 성능에 영향을 미치지 않아 직관적으로 이해되도록 코딩을 구현해봤습니다.
'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글
| [백준 14501번] 퇴사 (조합) (0) | 2021.04.20 |
|---|---|
| [백준 14891번] 톱니바퀴 (시뮬레이션) (0) | 2021.04.17 |
| [백준 15685번] 드래곤 커브 (시뮬레이션) (0) | 2021.04.16 |
| [백준 14888번] 연산자 끼워넣기 (순열) (0) | 2021.04.16 |
| [백준 14503번] 로봇 청소기 (시뮬레이션) (0) | 2021.04.16 |
댓글