알고리즘 모음(C++)

백준 15683 - 감시(C++) 본문

백준

백준 15683 - 감시(C++)

공대생의 잡다한 사전 2021. 12. 20. 11:50

문제 링크입니다. https://www.acmicpc.net/problem/15683

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

삼성 SW 역량 테스트 기출문제 였습니다.

문제에서 주어진 조건대로 구현하면 풀 수 있는 문제였습니다. 구현 문제에 익숙하지 않으시다면 어려울 것 같습니다.

모든 경우를 탐색해야 함으로 DFS를 통해 확인했습니다.

출력 예시

CCTV는 1번~5번까지 있습니다.

1번 -> 한방향

2번 -> 2방향(평행)

3번 -> 2방향(수직)

4번 -> 3방향

5번 -> 4방향

6번 -> 벽

MAP이 주어지고, CCTV과 벽이 주어질 때, 사각 지대의 최소 갯수를 구하는 문제였습니다.

 

N개의 CCTV가 있다고 했을 때, 각각의 CCTV는 4번을 돌려서 확인할 수 있음으로, N^4번을 확인해야 합니다.

DFS를 통해 모든 경우를 확인했는데, 해당 방법을 통해 확인한다면 다음과 같이 나타납니다.

1. 1번 동쪽 -> 2번 동쪽 -> 3번 동쪽 -> ..... -> N번 동쪽

2. 1번 동쪽 -> 2번 동쪽 -> 3번 동쪽 -> ..... -> N번 서쪽

3. 1번 동쪽 -> 2번 동쪽 -> 3번 동쪽 -> ..... -> N번 남쪽

4. 1번 동쪽 -> 2번 동쪽 -> 3번 동쪽 -> ..... -> N번 북쪽

5. 1번 동쪽 -> 2번 동쪽 -> 3번 동쪽 -> .... N-1번 서쪽 -> N번 동쪽

6. 1번 동쪽 -> 2번 동쪽 -> 3번 동쪽 -> .... N-1번 서쪽 -> N번 서쪽

(이러한 방법으로 모두 확인 가능하다.)

void dfs(int cnt) {
    if (cnt == C.size()) {
       min_remain = min(min_remain, find_blind_spot());
    }
    else {
        save_map(cnt);
        for (int i = 0; i < 4; i++) { 
            return_maps(cnt);
            fill_spot(C[cnt].x, C[cnt].y, C[cnt].method, i);
            dfs(cnt + 1); 
            
        }
    }
}

확인한 CCTV의 갯수가 N개가 될 때까지 DFS를 반복하고, 전부 확인했다면 빈칸의 갯수를 찾은뒤, 최소 갯수와 비교합니다.

 

 

DFS를 구현했다면, 1번~5번까지 CCTV의 작동을 만들어야 합니다.

1번과 2번을 만들었다면, 나머지 CCTV의 구현도 쉽게할 수 있습니다.

1번 CCTV는 한 방향으로만 볼 수 있습니다.

따라서, X 혹은 Y 좌표를 잡은 뒤, 해당 좌표를 +1, -1을 해주며 움직여줍니다. 

        int xx = x + 1;
        int yy = y;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            xx += 1;
        }

이 경우, 아래를 확인하는 경우입니다. 이와 같이 4방향을 만들어주면 됩니다.

 

2번 CCTV의 경우에는 2방향(평행)을 확인할 수 있습니다.

따라서 X의 좌표는 고정임으로, 움직이는 Y좌표 2개를 만들어서 +1, -1를 각각해줍니다.

        int xx = x;
        int yy = y + 1;
        int yy2 = y - 1;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            yy += 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 -= 1;
        }

이 경우는 가로를 확인하는 경우입니다. 세로또한 X좌표를 움직이며 확인하면 됩니다.

 

 

여기서 주의할 점은, Map은 바뀌면 안된다는 것입니다.

DFS를 통해 CCTV가 볼 수 있는 곳을 계속 바꾸기 때문에, Map 하나로만 확인을 한다면 움직임을 구현할 수 없습니다.

따라서 Map을 복사해 Copy_map을 만든 뒤, 해당 배열을 움직여줍니다.

또한 각 단계마다, Copy_map을 받아서, 각 방향을 탐색했을 때, 되돌려줘야합니다. 그래서 return_map 배열을 만들어서 각 단계마다 Copy_map의 값을 받아줬습니다.

 

 

문제 접근 방법

1. CCTV의 좌표 및 방향을 구조체 백터를 통해 저장한다.

2. DFS를 통해, 저장된 CCTV의 갯수만큼 확인한다.

3. 새로운 방향을 확인할 때마다, 전 단계의 Map으로 되돌린뒤 확인한다.

4. 모든 CCTV를 확인할 때마다 최소 갯수와 비교한다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

int N, M;
int min_remain = 999;
int map[9][9]; // 0 - 빈칸, 1~5 - CCTV, 6 - 벽
int copy_map[9][9];
int return_map[9][9][65];
typedef struct cctv {
    int x;
    int y;
    int method;
}cctv;
vector<cctv> C;

void method_1(int x, int y, int way) {
    if (way == 0) {
        int xx = x + 1;
        int yy = y;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            xx += 1;
        }
    }
    else if (way == 1) {
        int xx = x - 1;
        int yy = y;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            xx -= 1;
        }
    }
    else if (way == 2) {
        int xx = x;
        int yy = y + 1;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            yy += 1;
        }
    }
    else {
        int xx = x;
        int yy = y - 1;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            yy -= 1;
        }
    }
}

void method_2(int x, int y, int way) {
    if (way == 0 || way == 2) {
        int xx = x;
        int yy = y + 1;
        int yy2 = y - 1;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            yy += 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 -= 1;
        }
    }
    else {
        int yy = y;
        int xx = x + 1;
        int xx2 = x - 1;
        while (1) {
            if (xx < 1 || yy < 1 || xx > N || yy > M || map[xx][yy] == 6) break;
            copy_map[xx][yy] = 9;
            xx += 1;
        }
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 -= 1;
        }
    }
}

void method_3(int x, int y, int way) {
    if (way == 0) {
        int xx = x;
        int xx2 = x - 1;
        int yy = y;
        int yy2 = y + 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 -= 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 += 1;
        }
    }
    else if (way == 1) {
        int xx = x;
        int xx2 = x + 1;
        int yy = y;
        int yy2 = y + 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 += 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 += 1;
        }
    }
    else if (way == 2) {
        int xx = x;
        int xx2 = x + 1;
        int yy = y;
        int yy2 = y - 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 += 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 -= 1;
        }
    }
    else {
        int xx = x;
        int xx2 = x - 1;
        int yy = y;
        int yy2 = y - 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 -= 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 -= 1;
        }
    }
}

void method_4(int x, int y, int way) {
    if (way == 0) {
        int xx = x;
        int xx2 = x - 1;
        int yy = y;
        int yy2 = y + 1;
        int yy3 = y - 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 -= 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 += 1;
        }
        while (1) {
            if (xx < 1 || yy3 < 1 || xx > N || yy3 > M || map[xx][yy3] == 6) break;
            copy_map[xx][yy3] = 9;
            yy3 -= 1;
        }
    }
    else if (way == 1) {
        int xx = x;
        int xx2 = x - 1;
        int xx3 = x + 1;
        int yy = y;
        int yy2 = y + 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 -= 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 += 1;
        }
        while (1) {
            if (xx3 < 1 || yy < 1 || xx3 > N || yy > M || map[xx3][yy] == 6) break;
            copy_map[xx3][yy] = 9;
            xx3 += 1;
        }
    }
    else if (way == 2) {
        int xx = x;
        int xx2 = x + 1;
        int yy = y;
        int yy2 = y + 1;
        int yy3 = y - 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 += 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 += 1;
        }
        while (1) {
            if (xx < 1 || yy3 < 1 || xx > N || yy3 > M || map[xx][yy3] == 6) break;
            copy_map[xx][yy3] = 9;
            yy3 -= 1;
        }
    }
    else {
        int xx = x;
        int xx2 = x - 1;
        int xx3 = x + 1;
        int yy = y;
        int yy2 = y - 1;
        while (1) {
            if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
            copy_map[xx2][yy] = 9;
            xx2 -= 1;
        }
        while (1) {
            if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
            copy_map[xx][yy2] = 9;
            yy2 -= 1;
        }
        while (1) {
            if (xx3 < 1 || yy < 1 || xx3 > N || yy > M || map[xx3][yy] == 6) break;
            copy_map[xx3][yy] = 9;
            xx3 += 1;
        }
    }
}

void method_5(int x, int y, int way) {
    int xx = x;
    int xx2 = x - 1;
    int xx3 = x + 1;
    int yy = y;
    int yy2 = y + 1;
    int yy3 = y - 1;
    while (1) {
        if (xx2 < 1 || yy < 1 || xx2 > N || yy > M || map[xx2][yy] == 6) break;
        copy_map[xx2][yy] = 9;
        xx2 -= 1;
    }
    while (1) {
        if (xx < 1 || yy2 < 1 || xx > N || yy2 > M || map[xx][yy2] == 6) break;
        copy_map[xx][yy2] = 9;
        yy2 += 1;
    }
    while (1) {
        if (xx3 < 1 || yy < 1 || xx3 > N || yy > M || map[xx3][yy] == 6) break;
        copy_map[xx3][yy] = 9;
        xx3 += 1;
    }
    while (1) {
        if (xx < 1 || yy3 < 1 || xx > N || yy3 > M || map[xx][yy3] == 6) break;
        copy_map[xx][yy3] = 9;
        yy3 -= 1;
    }
}

void fill_spot(int x, int y, int method, int way) {
    if (method == 1) method_1(x, y, way);
    else if (method == 2) method_2(x, y, way);
    else if (method == 3) method_3(x, y, way);
    else if (method == 4) method_4(x, y, way);
    else method_5(x, y, way);
}

void return_maps(int cnt) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            copy_map[i][j] = return_map[i][j][cnt];
        }
    }
}

void save_map(int cnt) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            return_map[i][j][cnt] = copy_map[i][j];
        }
    }
}

int find_blind_spot() {
    int remain = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (copy_map[i][j] == 0) {
                remain++;
            }
        }
    }
    return remain;
}

void dfs(int cnt) {
    if (cnt == C.size()) {
       min_remain = min(min_remain, find_blind_spot());
    }
    else {
        save_map(cnt);
        for (int i = 0; i < 4; i++) { 
            return_maps(cnt);
            fill_spot(C[cnt].x, C[cnt].y, C[cnt].method, i);
            dfs(cnt + 1); 
            
        }
    }
}

void solve() {
    dfs(0);
    cout << min_remain;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            copy_map[i][j] = map[i][j];
            if (map[i][j] >= 1 && map[i][j] <= 5) {
                C.push_back({ i,j,map[i][j] });
            }
        }
    }
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!

저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

백준 20056 - 마법사 상어와 파이어볼(C++)  (0) 2021.12.26
백준 21609 - 상어 중학교(C++)  (0) 2021.12.22
백준 16933 - 벽 부수고 이동하기 3(C++)  (0) 2021.11.20
백준 17219 - 비밀번호 찾기(C++)  (0) 2021.11.19
백준 5525 - IOIOI(C++)  (0) 2021.11.19
'백준' Related Articles more