[백준] 15683번 : 감시

문제

 

---

풀이

 

이 문제의 풀이를 쓰는 이유는...

문제를 풀고 다른 사람들의 풀이가 궁금해서 블로그를 봤더니 거의 다 하드코딩(?)을 했더라

내가 짠게 엄청 좋아보이진 않지만 그래도 최대한 효율적으로 쓰려고 노력해서 올려본다.

 

말로 설명하기가 좀 그래서 코드를 보면서 설명하려는데 그 전에 이걸 봐두면 좋다.

내 코드에선 각 cctv의 범위가 이렇게 세트로 묶여 있다.

무슨 말인지는 코드를 보면 이해될 것이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int, int> pp;

int N, M, result = 65;
vector<vector<int>> board;
vector<pp> cctv; //cctv 위치
pp direction[4] = {{-1, 0},   //상
                   {0,  1},   //우
                   {1,  0},   //하
                   {0,  -1}}; //좌

void ray(pp pos, int dir) {
    int row = pos.first;
    int col = pos.second;
    while (true) { //특정 방향으로 뻗어나가며 cctv의 범위 확인
        row += direction[dir].first;
        col += direction[dir].second;
        if ((row < 0) || (row >= N) || (col < 0) || (col >= M) || (board[row][col] == 6)) //범위를 벗어나거나 벽
            break;
        if (board[row][col] == 0) //다른 cctv를 지우지 않기 위해 빈 공간일 때만 방문 표시
            board[row][col] = 7;
    }
}

void install(pp pos, int dir) {
    int cur = board[pos.first][pos.second];
    if (cur >= 1) //1, 2, 3, 4, 5번 cctv
        ray(pos, dir);
    if (cur >= 2 && cur != 3) //2, 4, 5번 cctv
        ray(pos, (dir + 2) % 4);
    if (cur >= 3) //3, 4, 5번 cctv
        ray(pos, (dir + 1) % 4);
    if (cur == 5) //5번 cctv
        ray(pos, (dir + 3) % 4);
}

void backtracking(int idx) {
    if (idx == cctv.size()) { //모든 cctv 배치
        int cnt = 0; //사각지대 세기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0)
                    cnt++;
            }
        }
        result = min(result, cnt); //최솟값 갱신
        return;
    }
    vector<vector<int>> tmp = board; //복사
    int cur_cctv = board[cctv[idx].first][cctv[idx].second];
    for (int i = 0; i < 4; i++) {
        install(cctv[idx], i); //visited 처리
        backtracking(idx + 1); //재귀 호출
        board = tmp; //unvisited 처리
        if ((cur_cctv == 2 && i == 1) || (cur_cctv == 5 && i == 0)) //2번 cctv는 2개의 방향만, 5번 cctv는 1개의 방향만 체크
            break;
    }
}

int main() {
    cin >> N >> M;
    board.assign(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] > 0 && board[i][j] < 6) //cctv 입력
                cctv.emplace_back(i, j);
        }
    }
    backtracking(0);
    cout << result;
}

전체 소스코드다.

 

int N, M, result = 65;
vector<vector<int>> board;
vector<pp> cctv; //cctv 위치
pp direction[4] = {{-1, 0},   //상
                   {0,  1},   //우
                   {1,  0},   //하
                   {0,  -1}}; //좌

cctv의 좌표를 pair 벡터에 저장하고 각각의 방향을 저장한다.

상우하좌 시계방향으로 이동한다.

 

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] > 0 && board[i][j] < 6) //cctv 입력
                cctv.emplace_back(i, j);
        }
    }
    backtracking(0);

사무실의 상태를 입력받으면서 cctv라면 해당 위치를 저장한다. 그리고 백트래킹 함수를 호출한다.

 

void backtracking(int idx) {
    if (idx == cctv.size()) { //모든 cctv 배치
        int cnt = 0; //사각지대 세기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0)
                    cnt++;
            }
        }
        result = min(result, cnt); //최솟값 갱신
        return;
    }
    vector<vector<int>> tmp = board; //복사
    int cur_cctv = board[cctv[idx].first][cctv[idx].second];
    for (int i = 0; i < 4; i++) {
        install(cctv[idx], i); //visited 처리
        backtracking(idx + 1); //재귀 호출
        board = tmp; //unvisited 처리
        if ((cur_cctv == 2 && i == 1) || (cur_cctv == 5 && i == 0)) //2번 cctv는 2개의 방향만, 5번 cctv는 1개의 방향만 체크
            break;
    }
}

백트래킹 함수다.

 

    vector<vector<int>> tmp = board; //복사
    int cur_cctv = board[cctv[idx].first][cctv[idx].second];
    for (int i = 0; i < 4; i++) {
        install(cctv[idx], i); //visited 처리
        backtracking(idx + 1); //재귀 호출
        board = tmp; //unvisited 처리
        if ((cur_cctv == 2 && i == 1) || (cur_cctv == 5 && i == 0)) //2번 cctv는 2개의 방향만, 5번 cctv는 1개의 방향만 체크
            break;
    }

나중에 unvisited 처리를 하기 위해 tmp 배열에 현재 board의 상태를 저장한다.

이번에 설치할 cctv가 몇 번 cctv인지 cur_cctv에 저장한다.

 

cctv를 설치할 수 있는 방법은 기본적으로 4개 있다.

그래서 for문을 돌면서 4개의 방향에 cctv를 설치하고, 백트래킹 함수를 재귀 호출한다.

 

근데, 2번 cctv는 범위의 특성상 서로 다른 설치 방법이 2가지 뿐이고, 5번 cctv는 같은 이유로 설치 방법이 1가지다.

그래서 cur_cctv를 확인하며 불필요한 탐색을 하지 않도록 조건을 걸어 break한다.

 

그럼 cctv를 설치하는 install 함수를 보도록 하겠다.

 

void install(pp pos, int dir) {
    int cur = board[pos.first][pos.second];
    if (cur >= 1) //1, 2, 3, 4, 5번 cctv
        ray(pos, dir);
    if (cur >= 2 && cur != 3) //2, 4, 5번 cctv
        ray(pos, (dir + 2) % 4);
    if (cur >= 3) //3, 4, 5번 cctv
        ray(pos, (dir + 1) % 4);
    if (cur == 5) //5번 cctv
        ray(pos, (dir + 3) % 4);
}

이번에 설치한 cctv의 번호를 cur 변수에 담는다. dir이 1이라고 하자.

cur은 1~5일 것이다. 그렇기 때문에 1번 조건은 모두 통과한다.

 

다음 조건을 보면 cur이 2보다 크거나 같지만 3이어서는 안된다.

 

그 다음엔 cur이 3보다 크거나 같아야 한다.

 

마지막으로 cur이 5라면

 

이렇게 된다.

 

저 위에 풀이 쪽에 올린 표의 나머지 3개의 행도 이런 과정으로 채워진다.

아무튼 이렇게 찾은 cctv의 범위를 체크해줘야 한다. 그게 ray 함수다.

 

void ray(pp pos, int dir) {
    int row = pos.first;
    int col = pos.second;
    while (true) { //특정 방향으로 뻗어나가며 cctv의 범위 확인
        row += direction[dir].first;
        col += direction[dir].second;
        if ((row < 0) || (row >= N) || (col < 0) || (col >= M) || (board[row][col] == 6)) //범위를 벗어나거나 벽
            break;
        if (board[row][col] == 0) //다른 cctv를 지우지 않기 위해 빈 공간일 때만 방문 표시
            board[row][col] = 7;
    }
}

그냥 간단하게 특정 방향에 대해 범위를 벗어나거나 벽을 만날때까지 visited 표시(여기선 7)를 한다.

다만 원래 있던 cctv를 덮어쓸 수도 있으니 해당 공간이 빈 공간인 것을 확인하고 표시해야 한다.

 

    if (idx == cctv.size()) { //모든 cctv 배치
        int cnt = 0; //사각지대 세기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0)
                    cnt++;
            }
        }
        result = min(result, cnt); //최솟값 갱신
        return;
    }

다시 백트래킹 함수로 돌아와서 이런식으로 모든 cctv를 설치한 뒤, 사각지대를 확인하고 최솟값을 갱신하면 된다.