[백준/C++] 14502번: 연구소

 

17년도 삼성기출이다. 그리 어렵지 않을 줄 알았는데 머리 좀 써야된다..흑ㅠㅠ map이 크지 않기 때문에 어디에 벽을 둘 지를 부르트포스로 찾으면 되는데 나는 이 부분이 어려웠다. 3개의 벽을 찾았을 때마다 바이러스를 퍼트리도록 하도록 코딩하면 된다. 처음에는 3개의 벽을 다 배열에 담은 다음 그 후에 각 요소에 바이러스를 퍼트리도록 짜려고 했었는데 풀고보니 배열에 굳이 담을 필요없이 그때마다 처리해주면 된다는 것을 배웠다.

 

문제 풀이 순서

 

1) 3개의 벽의 자리를 선택해 벽을 세운다.

2) 바이러스를 퍼트린다.

3) 안전구역의 갯수를 센다.

4) 이를 vector에 담는다.

5) 이를 모든 조합에 대해 반복한다.

6) vector에서 최댓값을 찾아 출력한다.

 

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

int N, M;
int map[8][8];
int temp[8][8];
int temp_vir[8][8];
int visit[8][8] = { 0 };
vector<int> ans;

int dx[] = { 1,0,0,-1 };
int dy[] = { 0,1,-1,0 };


void copy(int (*a)[8], int(*b)[8]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            a[i][j] = b[i][j];
        }
    }
}

int cntSafe() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (temp_vir[i][j] == 0)cnt++;
        }
    }

    return cnt;
}

void transmit(int x, int y) {


    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= N || ny < 0 || ny >= M)continue;
        if (temp_vir[nx][ny] == 0 && visit[nx][ny]==0) {
            visit[nx][ny] == 1;
            temp_vir[nx][ny] = 2;
            transmit(nx, ny);
        }

    }
}


void virus_mainfunc() {

    copy(temp_vir, temp);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (temp_vir[i][j] == 2 && visit[i][j] == 0) {
                visit[i][j] = 1;
                transmit(i, j);

            }
        }
    }
    /*
    cout << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << temp_vir[i][j] << " ";
        }
        cout << endl;
    }
    */

    ans.push_back(cntSafe());
    memset(visit, 0, sizeof(visit));

}

void combi(int d) {

    if (d == 3) {
        virus_mainfunc();
        return;
    };

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (temp[i][j] == 0) {
                temp[i][j] = 1;
                combi(d + 1);
                temp[i][j] = 0;
            }
        }
    }

}


int main() {

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                copy(temp,map); //temp에 map의 정보를 복사
                temp[i][j] = 1;
                combi(1); //모든 조합에 대한 계산
                temp[i][j] = 0;

            }
        }
    }


    cout << *max_element(ans.begin(), ans.end());
    return 0;
}