백준 17141번 연구소 2[C++]

1. 문제 풀이

 문제 유형은 백트래킹 + 그래프 탐색입니다. 연구소의 도면을 입력받을 때, 벽을 제외한 칸들을 countOfBlank라는 변수에 저장했습니다. 그리고 2를 입력받은 위치 ( i, j )에 대해서 virus라는 pair <int, int>를 저장하는 벡터에 위치 정보를 삽입했습니다. 풀이에 대한 방법은 간단합니다. 백트래킹을 통해 virus에 저장된 위치 중 m개를 선택해 준 다음, 그래프 탐색을 돌리면 됩니다. 이때, flood fill과 최단 거리 갱신을 동시에 진행하고, flood fill 된 칸 수와 countOfBlank의 개수가 같은지 비교하는 처리를 해주면서 값을 반환하게 하는 방식을 사용했습니다. 

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 0x3f3f3f3f;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int n, m;
int board[55][55];

qpi q;
int countOfBlank;
int d[55][55];

vpi virus;
int ans{INF};
bool chk[15];

int bfs() {
    int cnt{}, mx{};
    memset(d, -1, sizeof(d));
    for(int i = 0; i < sz(virus); i++) {
        if(chk[i]) {
            d[virus[i].X][virus[i].Y] = 0;
            q.push(virus[i]);
        }
    }

    cnt = sz(q);

    while(sz(q)) {
        auto [cx, cy] = q.front(); q.pop();
        
        mx = max(mx, d[cx][cy]);

        for(int dir = 0; dir < 4; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(board[nx][ny] & 1 || (d[nx][ny] != -1 && d[nx][ny] <= d[cx][cy] + 1)) continue;
            cnt++;
            d[nx][ny] = d[cx][cy] + 1;
            q.push({nx, ny});
        }
    }

    return (cnt == countOfBlank ? mx : INF);
}

void select(int cur, int k) {
    if(k == m) {
        ans = min(ans, bfs());
        return;
    }

    for(int i = cur; i < sz(virus); i++) {
        if(chk[i]) continue;
        chk[i] = 1;
        select(i, k + 1); 
        chk[i] = 0;
    }
}

int main() {
    fastio(nullptr, false);

    memset(d, -1, sizeof(d));

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> board[i][j];
            if(!(board[i][j] & 1)) countOfBlank++;
            if(board[i][j] == 2) {
                virus.pb({i, j});
            }
        }
    }

    select(0, 0);

    cout << (ans == INF ? -1 : ans);
}

 

3. 제출 결과