[BOJ/백준 15683][C++] 감시

문제

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

백준 15683

백준 15683

백준 15683

 

문제 내용

N*M 크기의 사무실에, CCTV가 달려있고, CCTV는 벽을 넘어서 감시할 수 없다.

CCTV의 종류는 5가지가 있는데, 그 종류는 위의 문제에 나와 있다.

CCTV의 방향을 조절하여, 사각지대를 최소화하고자 한다.

 

문제 풀이

이 문제는 코드의 길이가 좀 길기는 하지만, 차근차근 진행하면 할 만하다.

구현해야 하는 순서는 아래와 같다.

1. 각각의 cctv 방향 결정하기 => 백트래킹 사용

2. 결정된 cctv의 방향대로, 감시 영역 표시하기

3. 사각지대 개수 세기

 

1. 각각의 cctv 방향 결정하기

1,3,4번 cctv는 방향이 4가지가 나오지만, 2번은 2가지, 5번은 1가지로 충분하기 때문에 range 변수로 for문의 범위를 제한해 줬다.

void decideCCTVDirection(int cnt) {
    if (cnt == originCCTV.size()) {
        mmin = min(mmin, calcCCTVRange());
        return;
    }

    resultCCTV[cnt] = originCCTV[cnt];

    int range;
    if (resultCCTV[cnt].cctvType == 5)
        range = 1;
    else if (resultCCTV[cnt].cctvType == 2)
        range = 2;
    else
        range = 4;

    for (int i = 0; i < range; i++) { // 방향 결정
        resultCCTV[cnt].direction = i;
        decideCCTVDirection(cnt + 1);
    }
}

 

2. 결정된 cctv의 방향대로, 감시 영역 표시하기

이 부분 코드가 길기는 한데, 비슷한 코드가 중복이 되어서 긴 것뿐이다.

상하좌우로 cctv 감시 영역을 표시하면 된다.

void drawLeft(int r, int c) {
    for (int i = c - 1; i >= 1; i--) {
        if (newArr[r][i] == 6) {
            return;
        } else if (newArr[r][i] == 0) {
            newArr[r][i] = -1; // #
        }
    }
}

void drawDown(int r, int c) {
    for (int i = r + 1; i <= n; i++) {
        if (newArr[i][c] == 6) {
            return;
        } else if (newArr[i][c] == 0) {
            newArr[i][c] = -1; // #
        }
    }
}

void drawRight(int r, int c) {
    for (int i = c + 1; i <= m; i++) {
        if (newArr[r][i] == 6) {
            return;
        } else if (newArr[r][i] == 0) {
            newArr[r][i] = -1; // #
        }
    }
}

void drawUp(int r, int c) {
    for (int i = r - 1; i >= 1; i--) {
        if (newArr[i][c] == 6) {
            return;
        } else if (newArr[i][c] == 0) {
            newArr[i][c] = -1; // #
        }
    }
}

void drawCCTVRange(CCTV cctv) {
    int r = cctv.r;
    int c = cctv.c;

    if (cctv.cctvType == 1) {
        switch (cctv.direction) {
        case 0:
            drawRight(r, c);
            break;
        case 1:
            drawDown(r, c);
            break;
        case 2:
            drawLeft(r, c);
            break;
        case 3:
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 2) {
        switch (cctv.direction) {
        case 0:
            drawRight(r, c);
            drawLeft(r, c);
            break;
        case 1:
            drawDown(r, c);
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 3) {
        switch (cctv.direction) {
        case 0:
            drawUp(r, c);
            drawRight(r, c);
            break;
        case 1:
            drawRight(r, c);
            drawDown(r, c);
            break;
        case 2:
            drawDown(r, c);
            drawLeft(r, c);
            break;
        case 3:
            drawLeft(r, c);
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 4) {
        switch (cctv.direction) {
        case 0:
            drawLeft(r, c);
            drawUp(r, c);
            drawRight(r, c);
            break;
        case 1:
            drawUp(r, c);
            drawRight(r, c);
            drawDown(r, c);
            break;
        case 2:
            drawRight(r, c);
            drawDown(r, c);
            drawLeft(r, c);
            break;
        case 3:
            drawDown(r, c);
            drawLeft(r, c);
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 5) {
        drawDown(r, c);
        drawLeft(r, c);
        drawRight(r, c);
        drawUp(r, c);
    }
}

 

3. 사각지대 개수 세기

2번에서 설명한 drawCCTVRange()를 수행한 이후, 0으로 남아있는 부분이 사각지대가 된다.

int calcCCTVRange() {
    newArr.assign(n + 1, vector<int>(m + 1, 0));
    copy(arr.begin(), arr.end(), newArr.begin());

    // 감시 영역 표시하기
    for (int i = 0; i < resultCCTV.size(); i++) {
        drawCCTVRange(resultCCTV[i]);
    }

    // 사각지대 개수 구하기
    int ssum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (newArr[i][j] == 0)
                ssum++;
        }
    }

    return ssum;
}

 

 

전체 코드

#include <iostream>
#include <vector>
using namespace std;

struct CCTV {
    int r;
    int c;
    int cctvType;  // 1~5
    int direction; // 0~3: 오른쪽, 아래, 왼쪽, 위
};

int n;
int m;
vector<vector<int>> arr;
vector<vector<int>> newArr;
vector<CCTV> originCCTV;
vector<CCTV> resultCCTV;
int mmin = 100;

void drawLeft(int r, int c) {
    for (int i = c - 1; i >= 1; i--) {
        if (newArr[r][i] == 6) {
            return;
        } else if (newArr[r][i] == 0) {
            newArr[r][i] = -1; // #
        }
    }
}

void drawDown(int r, int c) {
    for (int i = r + 1; i <= n; i++) {
        if (newArr[i][c] == 6) {
            return;
        } else if (newArr[i][c] == 0) {
            newArr[i][c] = -1; // #
        }
    }
}

void drawRight(int r, int c) {
    for (int i = c + 1; i <= m; i++) {
        if (newArr[r][i] == 6) {
            return;
        } else if (newArr[r][i] == 0) {
            newArr[r][i] = -1; // #
        }
    }
}

void drawUp(int r, int c) {
    for (int i = r - 1; i >= 1; i--) {
        if (newArr[i][c] == 6) {
            return;
        } else if (newArr[i][c] == 0) {
            newArr[i][c] = -1; // #
        }
    }
}

void drawCCTVRange(CCTV cctv) {
    int r = cctv.r;
    int c = cctv.c;

    if (cctv.cctvType == 1) {
        switch (cctv.direction) {
        case 0:
            drawRight(r, c);
            break;
        case 1:
            drawDown(r, c);
            break;
        case 2:
            drawLeft(r, c);
            break;
        case 3:
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 2) {
        switch (cctv.direction) {
        case 0:
            drawRight(r, c);
            drawLeft(r, c);
            break;
        case 1:
            drawDown(r, c);
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 3) {
        switch (cctv.direction) {
        case 0:
            drawUp(r, c);
            drawRight(r, c);
            break;
        case 1:
            drawRight(r, c);
            drawDown(r, c);
            break;
        case 2:
            drawDown(r, c);
            drawLeft(r, c);
            break;
        case 3:
            drawLeft(r, c);
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 4) {
        switch (cctv.direction) {
        case 0:
            drawLeft(r, c);
            drawUp(r, c);
            drawRight(r, c);
            break;
        case 1:
            drawUp(r, c);
            drawRight(r, c);
            drawDown(r, c);
            break;
        case 2:
            drawRight(r, c);
            drawDown(r, c);
            drawLeft(r, c);
            break;
        case 3:
            drawDown(r, c);
            drawLeft(r, c);
            drawUp(r, c);
            break;
        default:
            break;
        }
    } else if (cctv.cctvType == 5) {
        drawDown(r, c);
        drawLeft(r, c);
        drawRight(r, c);
        drawUp(r, c);
    }
}

int calcCCTVRange() {
    newArr.assign(n + 1, vector<int>(m + 1, 0));
    copy(arr.begin(), arr.end(), newArr.begin());

    // 감시 영역 표시하기
    for (int i = 0; i < resultCCTV.size(); i++) {
        drawCCTVRange(resultCCTV[i]);
    }

    // 사각지대 개수 구하기
    int ssum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (newArr[i][j] == 0)
                ssum++;
        }
    }

    return ssum;
}

void decideCCTVDirection(int cnt) {
    if (cnt == originCCTV.size()) {
        mmin = min(mmin, calcCCTVRange());
        return;
    }

    resultCCTV[cnt] = originCCTV[cnt];

    int range;
    if (resultCCTV[cnt].cctvType == 5)
        range = 1;
    else if (resultCCTV[cnt].cctvType == 2)
        range = 2;
    else
        range = 4;

    for (int i = 0; i < range; i++) { // 방향 결정
        resultCCTV[cnt].direction = i;
        decideCCTVDirection(cnt + 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    arr.assign(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];

            if (arr[i][j] != 0 && arr[i][j] != 6)
                originCCTV.push_back({i, j, arr[i][j], 0});
        }
    }

    resultCCTV.assign(originCCTV.size(), {0, 0, 0, 0});
    decideCCTVDirection(0);

    cout << mmin;
}