15683 감시

문제 링크

내 정답코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<pair<int, int>> cameras;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

// 사작 지대의 최소값 반환
// idx = 카메라 번호, c_map = 현재 촬영구역 공간 맵
int solve(int idx, vector<vector<int>> c_map) {
    int ret = 0;
    if (idx < cameras.size()) {
        ret = INT_MAX;
        int r = cameras[idx].first, c = cameras[idx].second;
        int curVal = c_map[r][c]; // 현재 IDX의 카메라 값
        switch (curVal) {
        case 1: // 직선형 
            for (int d = 0; d < 4; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 2: // 양방향 형
            for (int d = 0; d < 2; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[d + 2];
                    new_c = new_c + dc[d + 2];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 3: // └ 모양
            for (int d = 0; d < 4; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[(d + 1) % 4];
                    new_c = new_c + dc[(d + 1) % 4];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 4: // ┴ 모양
            for (int d = 0; d < 4; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[(d + 1) % 4];
                    new_c = new_c + dc[(d + 1) % 4];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[(d + 3) % 4];
                    new_c = new_c + dc[(d + 3) % 4];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 5: // ┼ 모양
            vector<vector<int>> new_map = c_map;

            for (int d = 0; d < 4; d++) {
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
            }
            ret = min(ret, solve(idx + 1, new_map));
            break;
        }
    }
    else {
        // 현재 사각지대의 수를 계싼한다.
        for (int r = 0; r < N; r++) for (int c = 0; c < M; c++) {
            if (!c_map[r][c])
                ret += 1;
        }
    }
    return ret;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    vector<vector<int>> c_map(N, vector<int>(M, 0));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            cin >> c_map[r][c];
            if (c_map[r][c] > 0 && c_map[r][c] != 6)
                cameras.push_back(make_pair(r, c));
        }
    }

    cout << solve(0, c_map) << "\n";
}

dfs를 진행하며 매번 맵을 복제하는 것 보다 카메라 정보를 저장했다가 마지막에 정보를 기반으로 감시구역을 지워나가는게 좋다.

다른사람 코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
vector<pair<int, int>> cameras;
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

// 사작 지대의 최소값 반환
// idx = 카메라 번호, c_map = 현재 촬영구역 공간 맵
int solve(int idx, vector<vector<int>> c_map) {
    int ret = 0;
    if (idx < cameras.size()) {
        ret = INT_MAX;
        int r = cameras[idx].first, c = cameras[idx].second;
        int curVal = c_map[r][c]; // 현재 IDX의 카메라 값
        switch (curVal) {
        case 1: // 직선형 
            for (int d = 0; d < 4; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 2: // 양방향 형
            for (int d = 0; d < 2; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[d + 2];
                    new_c = new_c + dc[d + 2];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 3: // └ 모양
            for (int d = 0; d < 4; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[(d + 1) % 4];
                    new_c = new_c + dc[(d + 1) % 4];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 4: // ┴ 모양
            for (int d = 0; d < 4; d++) {
                vector<vector<int>> new_map = c_map;
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[(d + 1) % 4];
                    new_c = new_c + dc[(d + 1) % 4];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                new_r = r;
                new_c = c;
                while (true) {
                    new_r = new_r + dr[(d + 3) % 4];
                    new_c = new_c + dc[(d + 3) % 4];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
                ret = min(ret, solve(idx + 1, new_map));
            }
            break;

        case 5: // ┼ 모양
            vector<vector<int>> new_map = c_map;

            for (int d = 0; d < 4; d++) {
                int new_r = r;
                int new_c = c;
                while (true) {
                    new_r = new_r + dr[d];
                    new_c = new_c + dc[d];
                    // 바깥이나 테두리를 나갈경우
                    if (new_r < 0 || new_c < 0 || new_r == N || new_c == M || new_map[new_r][new_c] == 6)
                        break;
                    else if (!new_map[new_r][new_c]) { // 0인 경우 사각지대가 하나 줄어든다
                        new_map[new_r][new_c] = -1;
                    }
                }
            }
            ret = min(ret, solve(idx + 1, new_map));
            break;
        }
    }
    else {
        // 현재 사각지대의 수를 계싼한다.
        for (int r = 0; r < N; r++) for (int c = 0; c < M; c++) {
            if (!c_map[r][c])
                ret += 1;
        }
    }
    return ret;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    vector<vector<int>> c_map(N, vector<int>(M, 0));
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            cin >> c_map[r][c];
            if (c_map[r][c] > 0 && c_map[r][c] != 6)
                cameras.push_back(make_pair(r, c));
        }
    }

    cout << solve(0, c_map) << "\n";
}