백준 17141번 연구소 2 C++

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

17141번: 연구소 2

 

bfs + 백트래킹

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long; 

struct Info {
    int row;
    int col;
    int moveCnt;
};

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

int n, m;
int emptyCnt = 0;
int ans = 987654321;
vector<vector<int>> board;
vector<vector<bool>> found;
vector<pair<int, int>> virusBoard;

vector<int> virusIdxs;
vector<bool> visited;

void RefreshFound() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            found[i][j] = false;
        }
    }
}

void BT(int idx, int cnt) {
    if (cnt >= m) {
        RefreshFound();
        queue<Info> q;
        int infectCnt = 0;
        int maxMoveCnt = 0;
        for (auto a : virusIdxs) {
            int row = virusBoard[a].first;
            int col = virusBoard[a].second;
            q.push({ row,col,0 });
            found[row][col] = true;
        }
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            maxMoveCnt = max(maxMoveCnt, curr.moveCnt);
            infectCnt++;
            for (int i = 0; i < 4; i++) {
                int nextRow = curr.row + dRow[i];
                int nextCol = curr.col + dCol[i];
                if (nextRow < 0 || nextRow >= n) continue;
                if (nextCol < 0 || nextCol >= n) continue;
                if (found[nextRow][nextCol]) continue;
                if (board[nextRow][nextCol] == 1) continue;
                found[nextRow][nextCol] = true;
                q.push({ nextRow,nextCol,curr.moveCnt + 1 });
            }
        }
        if (infectCnt == emptyCnt) {
            ans = min(ans, maxMoveCnt);
        }
        return;
    }
    for (int i = idx; i < virusBoard.size(); i++) {
        if (visited[i]) continue;
        visited[i] = true;
        virusIdxs.push_back(i);
        BT(i + 1, cnt + 1);
        visited[i] = false;
        virusIdxs.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;
    board = vector<vector<int>>(n, vector<int>(n));
    found = vector<vector<bool>>(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            if (board[i][j] != 1) emptyCnt++;
            if (board[i][j] == 2) virusBoard.push_back({ i,j });
        }
    }
    visited = vector<bool>(virusBoard.size(), false);
    BT(0, 0);
    if (ans == 987654321) ans = -1;
    cout << ans;
}