백준 14502 연구소 c++

벽을 세워 바이러스를 막는 문제이다.
조합을 이용하여 어렵지 않게 해결했다.

아이디어

1. 벽 3개를 반드시 사용하고, 바이러스가 퍼진 뒤의 안전구역 최댓값을 구해야 한다.
2. 모든 경우의 수를 구하고 최댓값을 도출해야 하는 것이기 때문에 나는 모든 빈칸을 조사하고 
	그 중에서 3개를 선택하는 조합을 사용하여 모든 경우의 수를 조사했다.
3. 선택한 벽 3개를 추가하고 bfs를 통해 바이러스를 퍼뜨리고 난 후 안전구역 개수를 구한다.
4. 모든 경우의 수를 돌리고 최댓값을 도출한 뒤, 출력한다.

자료구조

1. 연구소 위치를 기록할 board와 경우의 수마다 돌릴 playBoard판을 만든다.
3. 방문 표시를 할 vis 배열을 선언한다.
4. 바이러스 좌표를 기록할 queue와 빈칸을 기록할 vector를 선언한다.

구현

1.board에 데이터를 입력받고, 데이터가 0인 경우를 blank vector에 추가한다.
2. blank 사이즈만큼 vector를 선언하고 1로 초기화해준 뒤, 3개를 제외하고 모두 0으로 fill해준다.
3. do while문을 사용해주고 next_permutation을 사용하여 모든 경우의 수를 조사한다.
4. do 문 안에서는 blank중 1인 인덱스, 즉 선택한 빈칸을 1(벽)로 채워준다.
5. bfs 돌린다.
6. playBoard나 vis, queue 초기화해준다.
7. 최댓값 도출하고 출력한다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int n, m;
int board[10][10];
int playBoard[10][10];
int vis[10][10];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> v;
vector<pair<int, int>> blank;

bool oob(int x, int y) {
    return x < 0 || x >= n || y < 0 || y >= m;
}
void ResetBoard() {
    for(int i = 0; i < n; i++) {
        fill(vis[i], vis[i]+m, 0);
        for(int j = 0; j < m; j++) {
            playBoard[i][j] = board[i][j];
            if(board[i][j] == 2) {
                v.push({i, j});
                vis[i][j] = 1;
            }
        }
    }
}

int bfs() {
    while(!v.empty()) {
        int x, y; tie(x, y) = v.front(); v.pop();
        for(int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(oob(nx, ny)) continue;
            if(vis[nx][ny] || playBoard[nx][ny] != 0) continue;
            playBoard[nx][ny] = 2;
            vis[nx][ny] = 1;
            v.push({nx, ny});
        }
    }
    int sum = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(playBoard[i][j] == 0) sum++;
        }
    }
    return sum;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    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] == 0) blank.push_back({i, j});
        }
    }
    vector<int> brute(blank.size(), 1);
    // 0인 것을 선택
    fill(brute.begin(), brute.end()-3, 0);
    int mx = 0;
    do {
        ResetBoard();
        // 빈 칸 중에 3개를 선택해서 벽으로 만들기
        for(int i = 0; i < brute.size(); i++) {
            if(brute[i] == 1) {
                playBoard[blank[i].X][blank[i].Y] = 1;
            }
        }
        mx = max(mx, bfs());
    } while(next_permutation(brute.begin(), brute.end()));
    cout << mx;
}

실수

1. vector 선언할 때 반드시 초기화를 해주자.
2. bfs 돌릴 때마다 queue도 초기화를 해주자.