[백준/Baekjoon] 15683 감시 C++ :: Brute force & Implementation & Back tracking

https://www.acmicpc.net/problem/15683

15683번: 감시

---

1. Logic

해당 문제의 조건을 보면 사무실의 범위가 최대 8 * 8로 아주 작은것을 알 수 있다. 그렇기 때문에 완전탐색으로 구현할 수 있다. 시간복잡도는 모든 사무실을 다 탐색할 경우 8 * 8, CCTV의 4방향을 다 탐색한다는 가정 하 최악의 경우 8 * 8 * 4 정도가 나올 것 같다.

 

먼저 각 cctv 타입 별 탐색할 수 있는 범위의 경우의 수는 

1번 CCTV : 상, 하, 좌, 우

2번 CCTV : {상, 하}, {좌, 우}

3번 CCTV : {상, 우}, {우, 하}, {하, 좌}, {좌, 상}

4번 CCTV : {좌, 상, 우}, {상, 우, 하}, {좌, 하, 우},{하, 좌, 상}

5번 CCTV : {좌, 상, 하, 우}

이렇게 탐색할 수 있다.

 

전체적인 풀이 로직을 본다면, 모든 CCTV에 대해서 탐색할 수 있는 방향을 돌면서 DFS를 사용하여 벽끝까지 이동한다. 이후 탐색이 끝나면 남은 범위를 계산하여 최솟값을 낸다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

//좌, 상, 우, 하
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int n, m;
int loc[8][8];
vector<pair<int, int>> cctv;
int answer = 64;

void check(int y, int x, int dir) {
    dir %= 4;

    while(true) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        //while문이기 때문에 다음 같은열 다음 좌표를 구해주기 위해 다음 좌표값을 미리 넣어줌
        y = ny; x = nx;
        if (nx < 0 || ny < 0 || ny >= n || nx >= m)return;
        if (loc[ny][nx] == 6) return; //벽
        if (loc[ny][nx] != 0) continue; //cctv
        loc[ny][nx] = '#';
    }
}

void solve(int cnt) {
    if(cnt == cctv.size()) {
        int tempAnswer = 0; //현재 선택한 방향의 사각지대 최솟값 계산하여 저장
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(loc[i][j] == 0) tempAnswer++;
            }
        }
        answer = min(answer, tempAnswer);
        return;
    }

    int y = cctv[cnt].first;
    int x = cctv[cnt].second;
    //입력받은 배열을 임시 배열에 저장해서 계산 후 다시 돌려놔야함
    int backUpArr[8][8];

    //동, 서, 남, 북 4방향 회전
    for(int dir = 0; dir < 4; dir++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                backUpArr[i][j] = loc[i][j];
            }
        }

        if(loc[y][x] == 1) {
            check(y, x, dir + 2); //dir == 0일때 오른쪽
        }
        else if(loc[y][x] == 2) {
            check(y, x, dir); //dir == 0일때 왼쪽
            check(y, x, dir + 2); //dir == 0일때 오른쪽
        }
        else if(loc[y][x] == 3) {
            check(y, x, dir + 1); //dir == 0일때 위쪽
            check(y, x, dir + 2); //dir == 0일때 오른쪽
        }
        else if(loc[y][x] == 4) {
            check(y, x, dir); //dir == 0일때 왼쪽
            check(y, x, dir + 1); //dir == 0일때 위쪽
            check(y, x, dir + 2); //dir == 0일때 오른쪽
        }
        else if(loc[y][x] == 5) {
            check(y, x, dir); //dir == 0일때 왼쪽
            check(y, x, dir + 1); //dir == 0일때 위쪽
            check(y, x, dir + 2); //dir == 0일때 오른쪽
            check(y, x, dir + 3); //dir == 0일때 아래쪽
        }
        solve(cnt + 1);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                loc[i][j] = backUpArr[i][j];
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> loc[i][j];
            if(loc[i][j] >= 1 && loc[i][j] <= 5)
                cctv.push_back({i, j});
        }
    }
    solve(0);
    cout << answer;
}

 

 

---

3. Feedback

삼성이 보통 구현을 많이 낸다고해서 구현력을 높이기 위해 풀이를 하려고한다. 확실히 구현이 까다롭고 생각해야할 조건의 종류가 많은 것 같다. 처음에 실버 문제가 어려웠는데 지금은 풀 수 있는 것 처럼 이 또한 성장통이겠거니 하며 초심을 잃지 않고 꾸준히 풀어야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐