[BOJ] 17142 - 연구소 3

[백준] 17142 - 연구소 3

bfs를 돌릴 때마다 각각의 ck배열을 초기화해주어야 하는데 그렇지 않아서 이상한 답이 나와 당황했던 문제다. 언제나 초기화는 엄청 중요한 것이다..

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string.h>
#include <queue>
#include <functional>
#define INF 987654321
using namespace std;
typedef pair<int, int> PII;

const int dr[4] = { 1, -1, 0, 0 }, dc[4] = { 0,0,1,-1 };
int n, m, arr[55][55], ck[55][55];
vector<PII> v;

bool is_in_range(int x, int y) {
    return x >= 0 && x < n&& y >= 0 && y < n;
}

int bfs(int idx, int cnt, vector<PII> virus) {
    int rtn = INF;
    if (cnt == m) {
        int v_cnt = 1;
        memset(ck, 0, sizeof(ck));
        queue<PII> q;
        for (auto it : virus) {
            q.push(it);
            ck[it.first][it.second] = 1;
        }
        while (!q.empty()) {
            int xx = q.front().first, yy = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = xx + dr[i], y = yy + dc[i];
                if (is_in_range(x, y) && arr[x][y] != 1 && !ck[x][y]) {
                    ck[x][y] = ck[xx][yy] + 1;
                    q.push({ x, y });
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] != 0) continue;
                if (!ck[i][j]) return INF;
                v_cnt = max(v_cnt, ck[i][j]);
            }
        }
        return v_cnt - 1;
    }
    for (int i = idx + 1; i < v.size(); i++) {
        vector<PII> tmp = virus;
        tmp.push_back(v[i]);
        rtn = min(rtn, bfs(i, cnt + 1, tmp));
    }
    return rtn;
}

int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", arr[i] + j);
            if (arr[i][j] == 2) v.push_back({ i, j });
        }
    }
    int ans = bfs(-1, 0, vector<PII>());
    printf("%d", ans == INF ? -1 : ans);
    return 0;
}