[17142] 연구소 3

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

17142번: 연구소 3

<문제>

백트래킹 + BFS, 여기에 아래에 대한 예외처리를 요한다.

-> '0'으로 표현되는 빈칸과 달리, '*'로 표현되는 비활성 바이러스에 대한 탐색은 '가중치가 없다'.

 

정확히는, 빈칸에 대해서는 가중치가 1, 비활성바이러스에 대해서는 가중치가 0일때의 최단거리를 구해야한다.

 

이외의 조건은 상수시간내에 처리할 수 있는 조건들이다.

예를들어, '모든 빈칸에 바이러스를 퍼뜨릴 수 없다면 -1을 출력' 하는 조건은 빈칸의 개수를 미리 저장해두고

bfs가 종료된 후 비교하는 작업만 거치면 처리되는 부분이다.

 

 

지금은 사실 입력이 작아 어떠한 구현 방법을 선택해도 TLE이 나오지는 않을것으로 생각되었기에 일일히 dist를 저장해주고 매 bfs를 시작할때마다 초기화하는 방법을 선택했다.

dist의 최대값이 곧 해당 탐색에서 소요된 시간이라고 볼 수 있으나, 비활성 바이러스에 대한 가중치는 0이므로

dist중 비활성바이러스를 제외한 공간에서 최대값을 찾도록

turn을 업데이트하는 부분은 현재 위치한 곳이 빈칸이었을때에만 한정해야한다.

 

 

<소스코드>

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int INF = 2121212121;
int n, m, bfsStartSize, answer = INF, totalCnt;
int map[51][51], dist[51][51], dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
bool check[11];
vector<pair<int, int>>bfsStart;
queue <pair<int, int>>q;
int getScore(void) {
    int i, j, turn = 0, cnt = 0;
    while (!q.empty()) {
        pair<int, int>cur = q.front();
        q.pop();
        for (i = 0; i < 4; i++) {
            int nextY = cur.first + dy[i];
            int nextX = cur.second + dx[i];
            if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= n)continue;
            if (dist[nextY][nextX] == -1 && map[nextY][nextX] != 1) {
                q.push({ nextY,nextX });
                dist[nextY][nextX] = dist[cur.first][cur.second] + 1;
                if (map[nextY][nextX] == 0) {
                    cnt++;
                    turn = max(dist[nextY][nextX], turn);
                }
            }
        }
    }
    if (cnt == totalCnt)
        return turn;
    else
        return INF;
}
void f(int depth, int idx) {
    int i,j;
    if (depth == m) {
        //init start
        while (!q.empty())q.pop();
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                dist[i][j] = -1;
            }
        }
        for (i = 0; i < bfsStartSize; i++) {
            if (check[i] == true) {
                q.push({ bfsStart[i].first,bfsStart[i].second });
                dist[bfsStart[i].first][bfsStart[i].second] = 0;
            }
        }
        //init end    
        answer = min(getScore(), answer);
        return;
    }
    for (i = idx; i < bfsStartSize; i++) {
        if (check[i] == false) {
            check[i] = true;
            f(depth + 1, i + 1);
            check[i] = false;
        }
    }
    return;
}
int main(void) {
    int i, j;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 2) {
                bfsStart.push_back({ i,j });
            }
            else if (map[i][j] == 0) {
                totalCnt++;
            }
        }
    }
    bfsStartSize=bfsStart.size();
    f(0, 0);
    if (answer != INF)
        printf("%d", answer);
    else
        printf("-1");
    return 0;
}

getScore : BFS를 통해 바이러스의 확산을 진행한다.

모든 칸에 바이러스를 채운다면 소요된 시간을 반환하고, 모든 칸에 바이러스를 채울 수 없었다면 INF를 반환한다.

 

f : 백트래킹을 통해 활성화할 바이러스를 선택한다.

depth == m으로 선택이 종료되었다면 초기화를 진행하고 getScore함수를 호출해 정답까지 업데이트한다.