백준 17141 - 연구소 2

문제 : https://www.acmicpc.net/problem/17141

 

문제 요약

1. 연구소에 바이러스 M개를 놓아야 하며, 바이러스를 놓을 칸이 M <= X <= 10 개 만큼 주어진다.

2. 입력값 중 1은 벽이므로 이동할 수 없고, 모든 빈칸에 바이러스를 퍼뜨리는데 걸리는 최소 시간을 구하는 문제이다.

풀이과정

1. 값을 입력받을 때 바이러스를 놓을 수 있는 칸(2) 를 미리 저장해놓고, 빈칸의 개수를 미리 구해놓는다.

값이 2여도 바이러스가 놓여져 있는 칸은 아니며, 빈칸으로 생각해야 한다.

1-1. 만약 빈칸이 0이라면 0을 출력하고 마무리한다.

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            scanf("%d",&lab[i][j]);
            if(lab[i][j] == 2) virusq.push_back({i,j});
            if(lab[i][j] != 1) emptySize++;
        }
    }
    if(emptySize == 0) {
        printf("0\n");
        return 0;
    }

 

2. 바이러스를 M개만큼 선택해서 바이러스를 퍼뜨려야 한다. 이때 재귀호출하여 조합을 통해 아래와 같이 M개를 선택하고 bfs를 실행한다.

void solution(int cnt, int idx) {
    // 바이러스 선택 완료
    if(cnt == M) {
        result = spreadVirus();
        ans = (ans < result) ? ans : result;
        memset(visited,0,sizeof(visited));
    }
    for(int i=idx+1; i<virusq.size(); i++) {
        if(selected[i] == false) {
            selected[i] = true;
            solution(cnt+1,i);
            selected[i] = false;
        }
    }
}

int main() {
...
    for(int i=0; i<virusq.size(); i++) {
        if(selected[i] == false) {
            selected[i] = true;
            solution(1,i);
            selected[i] = false;
        }
    }
...
 }

 

3. bfs를 통해 최소시간을 구하면 해결할 수 있으나, 주의할 점은 이미 바이러스 놓을 자리를 선택했을 시점에 전부 퍼뜨렸는지 확인해야 한다. 

int spreadVirus() {
    deque < pair < int,int > > dq;
    int y,x,ny,nx;
    int spreaded = 0;
    for(int i=0; i<10; i++) {
        if(selected[i]) {
            y = virusq[i].first;
            x = virusq[i].second;
            dq.push_back({y,x});
            visited[y][x] = 1;
            spreaded++;
        }
    }

    // 이미 바이러스를 선택했을 때 전부 퍼뜨림
    if(spreaded == emptySize) return 0;

    while(!dq.empty()) {
        y = dq.front().first;
        x = dq.front().second;
        dq.pop_front();

        for(int i=0; i<4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(ny >= N || ny < 0 || nx >= N || nx < 0) continue;
            if(visited[ny][nx] || lab[ny][nx] == 1) continue;

            visited[ny][nx] = visited[y][x] + 1;
            dq.push_back({ny,nx});
            spreaded++;
            if(spreaded == emptySize) return visited[ny][nx] - 1;
        }
    }
    return INF;
}

 

 

코드

#include <iostream>
#include <stdio.h>
#include <deque>
#include <string.h>
using namespace std;
#define INF 987654321

int lab[50][50];
int visited[50][50];
bool selected[10];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int N,M;
int emptySize = 0;
int ans = INF, result;

deque < pair < int,int > > virusq;

int spreadVirus() {
    deque < pair < int,int > > dq;
    int y,x,ny,nx;
    int spreaded = 0;
    for(int i=0; i<10; i++) {
        if(selected[i]) {
            y = virusq[i].first;
            x = virusq[i].second;
            dq.push_back({y,x});
            visited[y][x] = 1;
            spreaded++;
        }
    }

    // 이미 바이러스를 선택했을 때 전부 퍼뜨림
    if(spreaded == emptySize) return 0;

    while(!dq.empty()) {
        y = dq.front().first;
        x = dq.front().second;
        dq.pop_front();

        for(int i=0; i<4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if(ny >= N || ny < 0 || nx >= N || nx < 0) continue;
            if(visited[ny][nx] || lab[ny][nx] == 1) continue;

            visited[ny][nx] = visited[y][x] + 1;
            dq.push_back({ny,nx});
            spreaded++;
            if(spreaded == emptySize) return visited[ny][nx] - 1;
        }
    }
    return INF;
}

void solution(int cnt, int idx) {
    // 바이러스 선택 완료
    if(cnt == M) {
        result = spreadVirus();
        ans = (ans < result) ? ans : result;
        memset(visited,0,sizeof(visited));
    }
    for(int i=idx+1; i<virusq.size(); i++) {
        if(selected[i] == false) {
            selected[i] = true;
            solution(cnt+1,i);
            selected[i] = false;
        }
    }
}

int main() {
    scanf("%d %d",&N,&M);
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            scanf("%d",&lab[i][j]);
            if(lab[i][j] == 2) virusq.push_back({i,j});
            if(lab[i][j] != 1) emptySize++;
        }
    }
    if(emptySize == 0) {
        printf("0\n");
        return 0;
    }

    for(int i=0; i<virusq.size(); i++) {
        if(selected[i] == false) {
            selected[i] = true;
            solution(1,i);
            selected[i] = false;
        }
    }
    
    (ans == INF) ? printf("-1\n") : printf("%d\n",ans);
}