[BOJ] 백준 15683번 : 감시 C++ : 아주정은

삼성 코딩테스트 준비하면서 푼 문제이다.

다른사람들은 다들 코드를 짧게 효율적으로 잘짜던데 나는 왜 안될까....

그래도 맞긴 맞았다.

dfs로 풀었는데, 트리구조에서 모든 노드 탐색하고 최소값 갱신해주는 형태로 풀었다.

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct pos {
    int x;
    int y;
};

int board[8][8];
int N, M;
int min_cnt = 100;

void count_zero(int p_board[8][8]) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (p_board[i][j] == 0)cnt++;
        }
    }
    if (min_cnt > cnt)min_cnt = cnt;
}


void dfs(int p_board[8][8], vector<pos> vec1, vector<pos> vec2, vector<pos> vec3, vector<pos> vec4, vector<pos> vec5) {
    int c_board[8][8];
    while (!vec5.empty()) {
        pos cur = vec5.back();
        vec5.pop_back();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                c_board[i][j] = p_board[i][j];
            }
        }
        for (int i = cur.x; i < N; i++) {
            if (c_board[i][cur.y] == 6) break;
            else {
                c_board[i][cur.y] = 7;
            }
        }
        for (int i = cur.x; i >= 0; i--) {
            if (c_board[i][cur.y] == 6) break;
            else {
                c_board[i][cur.y] = 7;
            }
        }
        for (int i = cur.y; i < M; i++) {
            if (c_board[cur.x][i] == 6)break;
            else {
                c_board[cur.x][i] = 7;
            }
        }
        for (int i = cur.y; i >= 0; i--) {
            if (c_board[cur.x][i] == 6)break;
            else {
                c_board[cur.x][i] = 7;
            }
        }
        dfs(c_board,vec1,vec2,vec3,vec4,vec5);
    }

    while (!vec4.empty()) {
        pos cur = vec4.back();
        vec4.pop_back();
        for (int a = 0; a < 4; a++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    c_board[i][j] = p_board[i][j];
                }
            }
            if (a == 0) {
                for (int i = cur.x; i >= 0; i--) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.x; i < N; i++) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i >= 0; i--) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            else if (a == 1) {
                for (int i = cur.x; i >= 0; i--) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.x; i < N; i++) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i < M; i++) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            else if (a == 2) {
                for (int i = cur.x; i < N; i++) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i < M; i++) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
                for (int i = cur.y; i >= 0; i--) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            else if (a == 3) {
                for (int i = cur.x; i >= 0; i--) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i < M; i++) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
                for (int i = cur.y; i >= 0; i--) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            dfs(c_board, vec1, vec2, vec3, vec4, vec5);
        }
    }

    while (!vec3.empty()) {
        pos cur = vec3.back();
        vec3.pop_back();
        for (int a = 0; a < 4; a++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    c_board[i][j] = p_board[i][j];
                }
            }
            if (a == 0) {
                for (int i = cur.x; i < N; i++) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i < M; i++) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            else if (a == 1) {
                for (int i = cur.x; i >=0; i--) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i < M; i++) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            else if (a == 2) {
                for (int i = cur.x; i < N; i++) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i >=0; i--) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            else if (a == 3) {
                for (int i = cur.x; i >= 0; i--) {
                    if (c_board[i][cur.y] == 6)break;
                    c_board[i][cur.y] = 7;
                }
                for (int i = cur.y; i >= 0; i--) {
                    if (c_board[cur.x][i] == 6)break;
                    c_board[cur.x][i] = 7;
                }
            }
            dfs(c_board, vec1, vec2, vec3, vec4, vec5);
        }
    }

    while (!vec2.empty()) {
        pos cur = vec2.back();
        vec2.pop_back();
        for (int a = 0; a < 2; a++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    c_board[i][j] = p_board[i][j];
                }
            }
            if (a == 0) {
                for (int i = cur.x; i < N; i++) {
                    if (c_board[i][cur.y] == 6)break;
                    else {
                        c_board[i][cur.y] = 7;
                    }
                }
                for (int i = cur.x; i >=0; i--) {
                    if (c_board[i][cur.y] == 6)break;
                    else {
                        c_board[i][cur.y] = 7;
                    }
                }
            }
            else if (a == 1) {
                for (int i = cur.y; i < M; i++) {
                    if (c_board[cur.x][i] == 6)break;
                    else {
                        c_board[cur.x][i] = 7;
                    }
                }
                for (int i = cur.y; i >= 0; i--) {
                    if (c_board[cur.x][i] == 6)break;
                    else {
                        c_board[cur.x][i] = 7;
                    }
                }
            }
            dfs(c_board, vec1, vec2, vec3, vec4, vec5);
        }
    }

    while (!vec1.empty()) {
        pos cur = vec1.back();
        vec1.pop_back();
        for (int a = 0; a < 4; a++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    c_board[i][j] = p_board[i][j];
                }
            }
            if (a == 0) {
                for (int j = cur.x; j < N; j = j + 1) {
                    if (c_board[j][cur.y] == 6)break;
                    else {
                        c_board[j][cur.y] = 7;
                    }
                }
            }
            else if (a == 2) {
                for (int j = cur.x; j >= 0; j = j - 1) {
                    if (c_board[j][cur.y] == 6)break;
                    else {
                        c_board[j][cur.y] = 7;
                    }
                }
            }
            else if (a == 3) {
                for (int j = cur.y; j < M; j++) {
                    if (c_board[cur.x][j] == 6)break;
                    else {
                        c_board[cur.x][j] = 7;
                    }
                }
            }
            else {
                for (int j = cur.y; j >= 0; j--) {
                    if (c_board[cur.x][j] == 6)break;
                    else {
                        c_board[cur.x][j] = 7;
                    }
                }
            }
            dfs(c_board,vec1,vec2,vec3,vec4,vec5);
        }
    }
    count_zero(p_board);
}


int main() {
    vector<pos> vec1, vec2, vec3, vec4, vec5;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] == 1) {
                vec1.push_back({ i,j,0 });
            }
            else if (board[i][j] == 2) {
                vec2.push_back({ i,j });
            }
            else if (board[i][j] == 3) {
                vec3.push_back({ i,j });
            }
            else if (board[i][j] == 4) {
                vec4.push_back({ i,j });
            }
            else if (board[i][j] == 5) {
                vec5.push_back({ i,j });
            }
        }
    }

    dfs(board,vec1,vec2,vec3,vec4,vec5);
    cout << min_cnt << endl;
}