BJ17142 연구소3

BJ17142 연구소3

2020.02.11

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

Solution

• inMap : input NxN map
• checkMap : BFS를 위한 bool map
• numBlank : 총 빈칸 갯수
• myV : 바이러스 후보 좌표들
• myQ : BFS를 위한 큐
• vInfo : 완전탐색을 통해 얻은 0~M 까지의 활성화시킬 바이러스 index 정보
• 알고리즘
  • getResult 함수를 통해 완전탐색하여 0번 ~ myV.size()-1번 까지의 바이러스 중 M개를 고른다.
  • (조합) 조합을 다 골랐다면(기저조건) BFS를 호출하여 탐색에 걸린 시간을 받아온다.
  • 탐색했는데 빈칸이 존재한다면 INF를 리턴하여 실패했음을 알린다.
  • 매 재귀호출에서 받아온 결과들 중 가장 최소를 반환하도록 하여 최솟값을 반환한다.
  • 만약 최종 결과가 INF 라면 불가능한 경우로, -1을 출력한다.

코드

//! 2020.02.11
// TODO BJ17142_연구소3
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;
const int MAX = 55;
const int INF = 987654321;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
int N, M;
int inMap[MAX][MAX];
bool checkMap[MAX][MAX];
int numBlank;
vector <pair<int, int>> myV;
queue <pair<int, int>> myQ;
int vInfo[15];

bool inRange(int y, int x) {
    if (y >= 0 && y < N && x >= 0 && x < N) return true;
    else return false;
}

int BFS() {
    int cnt = 0;
    int t = -1;
    for (int i = 0; i < M; i++) {
        int idx = vInfo[i];
        int y = myV[idx].first;
        int x = myV[idx].second;
        checkMap[y][x] = true;
        myQ.push(make_pair(y, x));
    }

    while (!myQ.empty() && cnt<numBlank) {
        t++;
        int sizeQ = myQ.size();
        for (int i = 0; i < sizeQ; i++) {
            pair <int, int> current = myQ.front();
            myQ.pop();
            if (inMap[current.first][current.second] == 0) cnt++;

            for (int dir = 0; dir < 4; dir++) {
                int nextY = current.first + dy[dir];
                int nextX = current.second + dx[dir];
                if (inRange(nextY, nextX)) {
                    if (!checkMap[nextY][nextX] && inMap[nextY][nextX]!=1){
                        checkMap[nextY][nextX] = true;
                        myQ.push(make_pair(nextY, nextX));
                    }
                }
            }
        }
    }
    queue <pair<int, int>> empty;
    empty.swap(myQ);

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

    if (cnt < numBlank) return INF;
    else return t;
}

int getResult(int n, int prev) {
    if (n >= M) {
        return BFS();
    }
    else {
        int minResult = INF;
        for (int i = prev + 1; i < myV.size(); i++) {
            vInfo[n] = i;
            int tmpResult = getResult(n + 1, i);
            if (tmpResult < minResult) minResult = tmpResult;
        }
        return minResult;
    }
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &inMap[i][j]);
            if (inMap[i][j] == 2) myV.push_back(make_pair(i, j));
            else if (inMap[i][j] == 0) numBlank++;
        }
    }

    if (numBlank == 0) printf("%d\n", 0);
    else {
        int result = getResult(0, -1);
        if (result > 3000) result = -1;
        printf("%d\n", result);
    }
    return 0;
}

실수

BFS 함수에서 빈칸인 0만 탐색하도록 만들었었다. 주어진 예제는 모두 통과하였지만 문제의 조건인, 비활성화 되있는 바이러스에 도착하면 활성화된다는 조건을 빠뜨린 것이다. 반례가 존재한다.

2도 탐색하도록 하였는데 이렇게 되면 2가 끝인경우가 존재한다.

cnt 변수를 이용해서 방문한 곳이 빈칸인지 확인하도록 만들었고 처음 input을 받으면서 총 빈칸 개수를 세어놓도록 하였다. 두개의 변수를 비교해서 이미 빈칸을 채웠으면 while loop를 끝내도록 했다.

이렇게 했더니 Q가 빌 때 까지 탐색을 하지 않는 경우가 생겼고 다음 경우의 수에서 BFS를 할 때 문제가 생겼다. 그래서 empty Q를 만들어 swap하여 해결하였다.

마지막으로 2와 1만 존재할 때 0이어야 하는 결과가 Q가 빌 때 까지 탐색하는 결과가 생겨버렸고, 빈칸이 없으면 함수를 호출하지 않고 바로 결과를 출력하도록 변경하여 해결하였다.