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

풀이 시간: 1h13m42s48(문제풀기) + 14m20s69(반례수정)

시간 복잡도: O((4^C)NM)

공간 복잡도: O(NM)

문제

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다.

(1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다.

0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

문제 풀이

1. CCTV 위치 전부 저장

2. CCTV를 전부 돌면서 깊이 우선 탐색(dfs) 진행 (dfs 재귀호출 -> CCTV 순차적으로 진행)

3. 이때 한 CCTV마다 모든 방향을 탐색해야하므로 백트래킹 (arr을 이전 배열 값으로 되돌리기)

4. CCTV를 전체 다 탐색했을 경우, 0의 개수를 세어 ans 값과 비교하여 더 작은 값으로 ans를 갱신

5. CCTV 종류별로(1~5번) 다른 방향 탐색

6. 5에서 종류별로 다른 방향 탐색할 때 이 또한 90도로 4번 돌아야 함

7. CCTV 감시할 때, 다음 위치가 0일 경우, CCTV 감시 가능한 위치라는 의미로 -1로 변경하여 해당 위치 표시

8. 만약 다음 위치가 6이거나 배열의 범위를 벗어날 경우 종료

 

위와 같은 방식으로 다음과 같이 구현했다.

초기 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, ans = 1e9;
vector<vector<int>> arr;
vector<pair<int, int>> cctv; // cctv 좌표
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; // 우좌상하

void watch(int cctvDir, int curX, int curY) {
    int nX = curX + dir[cctvDir][0];
    int nY = curY + dir[cctvDir][1];
    if (nX < 0 || nX >= N || nY < 0 || nY >= M || arr[nX][nY] == 6) return;
    if (arr[nX][nY] == 0) { arr[nX][nY] = -1; watch(cctvDir, nX, nY); }
}

void dfs(int num) {
    if (num == cctv.size()) { // cctv 다 돌았을 경우
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                if (arr[i][j] == 0) cnt++;
        ans = min(cnt, ans);
        return;
    }
    int curX = cctv[num].first;
    int curY = cctv[num].second;
    int curCCTV = arr[curX][curY];
    vector<vector<int>> temp; // 배열 임시 저장 (백트래킹)
    for (int i = 0; i < 4; ++i) { // 각 cctv를 90도, 4방향으로 돌리기
        temp = arr;
        switch (curCCTV) {
            case 1: // 1번
                watch(i, curX, curY);
                break;
            case 2: // 2번
                watch(i, curX, curY);
                watch((i + 1) % 4, curX, curY);
                break;
            case 3: // 3번
                watch(i, curX, curY);
                watch((i + 2) % 4, curX, curY);
                break;
            case 4: // 4번
                watch(i, curX, curY);
                watch((i + 1) % 4, curX, curY);
                watch((i + 2) % 4, curX, curY);
                break;
            case 5: // 5번
                watch(i, curX, curY);
                watch((i + 1) % 4, curX, curY);
                watch((i + 2) % 4, curX, curY);
                watch((i + 3) % 4, curX, curY);
                break;
        }
        dfs(num + 1);
        arr = temp;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    arr = vector<vector<int>>(N, vector<int>(M, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] != 0 && arr[i][j] != 6)
                cctv.push_back({i, j});
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}

 

그러나 예제 2번과 예제 4번의 답이 제대로 나오지 않았다.

대체 어느 것이 문제인지 확인해보다가, watch() 함수에서 문제점을 발견하였다.

 

문제에서는 CCTV는 CCTV를 통과할 수 있다고 되어있는데, 그 부분이 제대로 처리되지 않았다.

해당 위치가 6인 것과 0인 것에 대해서는 제대로 조건문을 처리하였는데 CCTV가 있는 숫자를 마주할 경우 그냥 watch() 함수를 종료해버리는 것이었다. 문제의 목적은 CCTV를 통과해서 탐색하는 것이므로, 6과 0을 제외한 숫자를 마주하였을 경우에도 다음 위치로 넘어갈 수 있도록 처리해야 한다. 단, 이때는 해당 배열을 -1로 변경하지 않고 그냥 다음으로 넘기면 된다.

따라서, watch() 함수 코드를 다음과 같이 수정하였다.

void watch(int cctvDir, int curX, int curY) {
    int nX = curX + dir[cctvDir][0];
    int nY = curY + dir[cctvDir][1];
    if (nX < 0 || nX >= N || nY < 0 || nY >= M || arr[nX][nY] == 6) return;
    if (arr[nX][nY] == 0) arr[nX][nY] = -1;
    watch(cctvDir, nX, nY);
}

그런데도 답이 틀렸다고 나와서 반례를 찾아봤다.

https://www.acmicpc.net/board/view/130543

글 읽기 - 반례모음

위 질문 게시판 글을 통해 찾았는데, 총 4개의 반례가 나왔다.

// 반례
4 5
0 0 0 6 0
6 0 6 0 0
2 6 0 0 0
0 0 6 0 3
답: 8

4 3
0 0 0
3 0 0
0 2 2
0 1 6
답: 1

5 5
6 6 6 6 6
6 0 6 3 0
0 0 0 0 6
6 6 0 6 2
0 0 2 6 0 
답: 5

3 3
3 0 0
0 0 0
0 0 0
답: 4

 

CCTV 감시하는 방향을 넘기는 과정에서 문제가 있는듯 했다.

 

위에 구현한 코드를 기준으로 2번 CCTV를 예로 들어서 어떤 것이 문제인지 설명하겠다.

만약 현재 i가 0, 즉 우(→)라면, 2번 CCTV의 경우에는 그 반대인 좌(←) 위치를 찾아야한다.

따라서 위 코드에서는 우(→), 좌(←), 상(↑), 하(↓) 순서대로 배열을 저장했기 때문에 그냥 i + 1을 하여 좌(←) 위치를 넘겨주었다.

그러나 문제는 for문을 돌렸을 때이다. for 문에서 i가 1인 경우를 생각해보자.

만약 현재 i가 1, 즉 좌(←)라면, 2번 CCTV의 경우에는 그 반대인 우(→) 위치를 찾아야한다.

하지만 난 그냥 i + 1로 넘겨주었기 때문에, 이제 그 다음 위치인 i + 1 부분에 우(→) 위치가 존재하여야 한다. 그러나 계산대로라면, i + 1 = 2이기 때문에, dir배열에서 인덱스 2의 위치는 상(↑)이다.

 

이와 같이, 문제는 for문을 돌렸을 때 계속 그 다음 위치가 해당 CCTV의 감시 방향에 맞게 올바르게 회전되지 못하고 있다는 것이다. 즉, dir 배열을 구현할 때, 순서대로 90도씩 회전된 위치가 그 다음 인덱스 위치에 존재해야 한다.

 

따라서, 수정은 다음과 같이 해야한다.

▪️ 우(→), 상(↑), 좌(←), 하(↓)

▪️ 우(→), 하(↓), 좌(←), 상(↑)

▪️ 좌(←), 상(↑), 우(→), 하(↓)

▪️ 좌(←), 하(↓), 우(→), 상(↑)

이 4가지 버전 중에 하나를 선택하여 하면 정답이 된다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, ans = 1e9;
vector<vector<int>> arr;
vector<pair<int, int>> cctv; // cctv 좌표
int dir[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; // 우상좌하

void watch(int cctvDir, int curX, int curY) {
    int nX = curX + dir[cctvDir][0];
    int nY = curY + dir[cctvDir][1];
    if (nX < 0 || nX >= N || nY < 0 || nY >= M || arr[nX][nY] == 6) return;
    if (arr[nX][nY] == 0) arr[nX][nY] = -1;
    watch(cctvDir, nX, nY);
}

void dfs(int num) {
    if (num == cctv.size()) { // cctv 다 돌았을 경우
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                if (arr[i][j] == 0) cnt++;
        ans = min(cnt, ans);
        return;
    }
    int curX = cctv[num].first;
    int curY = cctv[num].second;
    int curCCTV = arr[curX][curY];
    vector<vector<int>> temp; // 배열 임시 저장 (백트래킹)
    for (int i = 0; i < 4; ++i) { // 각 cctv를 90도, 4방향으로 돌리기
        temp = arr;
        switch (curCCTV) {
            case 1: // 1번
                watch(i, curX, curY);
                break;
            case 2: // 2번
                watch(i, curX, curY);
                watch((i + 2) % 4, curX, curY);
                break;
            case 3: // 3번
                watch(i, curX, curY);
                watch((i + 1) % 4, curX, curY);
                break;
            case 4: // 4번
                watch(i, curX, curY);
                watch((i + 1) % 4, curX, curY);
                watch((i + 2) % 4, curX, curY);
                break;
            case 5: // 5번
                watch(i, curX, curY);
                watch((i + 1) % 4, curX, curY);
                watch((i + 2) % 4, curX, curY);
                watch((i + 3) % 4, curX, curY);
                break;
        }
        dfs(num + 1);
        arr = temp;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    arr = vector<vector<int>>(N, vector<int>(M, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] != 0 && arr[i][j] != 6)
                cctv.push_back({i, j});
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}

 

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

15683번: 감시