백준 14502번: 연구소 (C++)

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

조합과 bfs가 합쳐진 문제인 연구소 시리즈의 첫번째 문제이다.

다른 연구소 문제를 해결했다면, 비슷한 아이디어로 무난하게 해결할 수 있다.

알고리즘은 다음과 같다.

1. 빈 공간(0인 위치)를 벡터에 모두 담아놓고 그 중 세개를 조합으로 뽑는다.

2. 조합으로 뽑은 곳의 값을 1로 (벽으로) 변경해준 이후에 bfs를 수행한다.

3. 방문되지 않은 지점(바이러스가 퍼지지 않은 지점)이면서 빈 공간인 부분의 수를 계산한다.

4. 수정한 map과 방문처리 배열을 초기화 시켜준다.

//map에 1을 세개 두고, 만들 수 있는 0의 최대 개수
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int R, C, m[9][9], arr[4];//빈공간 담은 벡터의 인덱스 저장
vector<pair<int, int> > v; //빈공간 저장 벡터
bool vis[9][9], isused[81];
int res = 0, st = 0;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void bfs(pair<int, int> start) {
    q.push({ start.first, start.second });
    vis[start.first][start.second] = true;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = cur.first + dr[i];
            int nc = cur.second + dc[i];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
            if (vis[nr][nc] || m[nr][nc] == 1) continue;
 
            q.push({ nr, nc });
            vis[nr][nc] = true;
        }
    }
}
void findSafe() {
    int cnt = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            if (!vis[i][j] && m[i][j] == 0) cnt++; //빈칸이면서 바이러스가 퍼지지 않은 곳 = 안전지점
 
    if (res < cnt)
        res = cnt;
}
void init() {
    for (int i = 0; i < 3; i++) {
        int j = arr[i];
        m[v[j].first][v[j].second] = 0; //벽 세웠던 부분 다시 빈칸으로
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            vis[i][j] = false;
        }
    }
}
void backTracking(int k) {
    if (k == 3) { //빈공간 중에서 세개 조합 뽑아서
        for (int i = 0; i < 3; i++) {
            int j = arr[i];
            m[v[j].first][v[j].second] = 1; //1로 바꿔주고
        }
 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (m[i][j] == 2 && !vis[i][j]) bfs({ i, j }); //bfs 실행
            }
        }
 
        findSafe(); //빈칸이면서 방문되지 않은 지점 검색
 
        init(); //map, vis 수정한 값 초기화
 
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            backTracking(k + 1);
            isused[i] = false;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            if (m[i][j] == 0) v.push_back({ i, j }); //빈공간 인덱스 미리 저장
        }
    }
 
    backTracking(0); //빈공간 인덱스 조합 검사
 
    cout << res;
    return 0;
}