백준 17142 연구소 3 (C++)

17142번: 연구소 3

bfs를 응용해서 풀어야하는 문제이다. 우선 문제를 잘 이해해야한다. 입력값으로 활성화된 바이러스 수 만큼만 bfs를 해주어야하므로 조합으로 바이러스를 선택해야한다. 이를 dfs로 구현하해주어 카운트가 M과 같을 경우 bfs를 해주었다. 여기서 중요한 점은 맵에 빈칸이 없을 경우 비활성화된 바이러스가 존재해도 bfs를 끝내야한다는 점이다. 입력 당시 0인 칸의 개수를 카운트하여 이를 사용해주었다. bfs를 돌며 만약 다음 위치가 0인 경우에만 카운트해주고 시간 또한 카운트해준다. 조합을 통해 얻은 위치들을 bfs를 돌려주며 가장 짧은 시간을 구해주고 이를 출력해주었다. 만약 0인 칸이 존재한다면 -1을 출력해주었다.
다른 사람의 풀이를 참고하였다. 비활성화 바이러스의 경우 시간을 추가하지 않는다는 아이디어를 생각해내지 못해 시간이 오래 걸렸다. 또한 오타를 찾지 못해 찾는 시간도 오래 걸렸다. 오타를 주의하고 여러 문제를 풀며 아이디어를 떠올리는 연습을 해야겠다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N, M, res = 987654321, em = 0;
int A[50][50];
int checkM[10];
vector<pair<int, int>> v;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void bfs() {
    queue<pair<pair<int, int>, int>> q;
    bool check[50][50];
    int count = 0;
    int zero = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            check[i][j] = false;
        }
    }

    for (int i = 0; i < v.size(); i++) {
        int y = v[i].first;
        int x = v[i].second;

        if (!checkM[i]) continue;

        q.push({ { y, x },0 });
        check[y][x] = true;
    }

    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int c = q.front().second;

        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
            if (A[ny][nx] == 1) continue;
            if (!check[ny][nx]) {
                if (A[ny][nx] == 0) {
                    zero++;
                    count = c + 1;
                }

                q.push({ {ny,nx},c + 1 });
                check[ny][nx] = true;
            }
        }
    }

    if (em == zero) {
        res = min(res, count);
    }
}

void dfs(int depth, int cnt) {
    if (cnt == M) {
        bfs();

        return;
    }

    for (int i = depth; i < v.size(); i++) {
        if (checkM[i]) continue;

        checkM[i] = true;
        dfs(i + 1, cnt + 1);
        checkM[i] = false;
    }
}

void solution() {
    dfs(0, 0);

    if (res == 987654321) {
        res = -1;
    }

    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;

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

            if (A[i][j] == 2) {
                v.push_back({ i,j });
            }
            else if (A[i][j] == 0) {
                em++;
            }
        }
    }

    solution();

    return 0;
}