백준 17142 연구소 3 C++

코테 노트/백준

백준 17142 연구소 3 C++

화요밍 2021. 8. 18. 21:53

728x90

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

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

최종 코드

GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ17142.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.

github.com

//
//  main.cpp
//  BJ17142
//
//  Created by 최화연 on 2022/04/12.
//

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int lab[50][50] = {0, };
int copy_lab[50][50] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int N, M;
int hole_cnt = 0;

vector<pair<int, int>> virus;
vector<pair<int, int>> active_virus;
int min_sec = -1;

void spread_virus() {
    memcpy(copy_lab, lab, sizeof(copy_lab));
    queue<pair<pair<int, int>, int>> q;
    for(int i=0; i<M; i++) {
        q.push({{active_virus[i].first, active_virus[i].second}, 0});
        copy_lab[active_virus[i].second][active_virus[i].first] = 3;
    }
    int hole = 0;
    
    while(!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int sec = q.front().second;
        q.pop();
        
        for(int d=0; d<4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            //비활성화 바이러스인 경우,
            if (copy_lab[ny][nx] == 2) {
                copy_lab[ny][nx] = 3;
                q.push({{nx, ny}, sec+1});
            }
            //빈 칸인 경우,
            else if (copy_lab[ny][nx] == 0) {
                copy_lab[ny][nx] = 3;
                q.push({{nx, ny}, sec+1});
                hole ++;
                if (hole == hole_cnt) {
                    if (min_sec == -1 || min_sec > sec+1) {
                        min_sec = sec+1;
                    }
                    return;
                }
            }
        }
    }
}

void pick_M_virus(int i, int cnt) {
    if (cnt == M) {
        spread_virus();
        return;
    }
    
    for (int j=i; j<virus.size(); j++) {
        active_virus.push_back({virus[j].first, virus[j].second});
        pick_M_virus(j+1, cnt+1);
        active_virus.pop_back();
    }
    
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> lab[i][j];
            if (lab[i][j] == 0) {
                hole_cnt ++;
            }
            else if (lab[i][j] == 2) {
                virus.push_back({j, i});
            }
        }
    }
    if (hole_cnt == 0) cout << 0 << endl;
    else {
        pick_M_virus(0, 0);
        cout << min_sec << endl;
    }

    return 0;
}

풀이 과정

풀이 시간 48분

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int lab[50][50] = {0, };
int copy_lab[50][50] = {0, };
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int N, M;
int hole_cnt = 0;

vector<pair<int, int>> virus;
vector<pair<int, int>> active_virus;
int min_sec = -1;

void spread_virus() {
    memcpy(copy_lab, lab, sizeof(copy_lab));
    queue<pair<pair<int, int>, int>> q;
    for(int i=0; i<M; i++) {
        q.push({{active_virus[i].first, active_virus[i].second}, 0});
        copy_lab[active_virus[i].second][active_virus[i].first] = 3;
    }
    int hole = 0;
    
    while(!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int sec = q.front().second;
        q.pop();
        
        for(int d=0; d<4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            //비활성화 바이러스인 경우,
            if (copy_lab[ny][nx] == 2) {
                copy_lab[ny][nx] = 3;
                q.push({{nx, ny}, sec+1});
            }
            //빈 칸인 경우,
            else if (copy_lab[ny][nx] == 0) {
                copy_lab[ny][nx] = 3;
                q.push({{nx, ny}, sec+1});
                hole ++;
                if (hole == hole_cnt) {
                    if (min_sec == -1 || min_sec > sec+1) {
                        min_sec = sec+1;
                    }
                    return;
                }
            }
        }
    }
}

void pick_M_virus(int i, int cnt) {
    if (cnt == M) {
        spread_virus();
        return;
    }
    
    for (int j=i; j<virus.size(); j++) {
        active_virus.push_back({virus[j].first, virus[j].second});
        pick_M_virus(j+1, cnt+1);
        active_virus.pop_back();
    }
    
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> lab[i][j];
            if (lab[i][j] == 0) {
                hole_cnt ++;
            }
            else if (lab[i][j] == 2) {
                virus.push_back({j, i});
            }
        }
    }
    if (hole_cnt == 0) cout << 0 << endl;
    else {
        pick_M_virus(0, 0);
        cout << min_sec << endl;
    }

    return 0;
}

이전 풀이

풀이 시간 1시간 49분

크게 세 가지 로직으로 나누어 문제를 풀었다.

바이러스 M개 뽑기 -> dfs 알고리즘을 활용하여 바이러스 M개의 조합을 만든다
바이러스 퍼뜨리기 -> bfs 알고리즘을 활용하여 뽑은 M개의 바이러스를 활성화 시켜 바이러스를 퍼뜨린다.
모든 빈 칸에 바이러스가 퍼졌는지 확인 -> 모든 빈 칸에 퍼졌다면 최소 시간을 갱신한다.

//
//  main.cpp
//  BJ17142
//
//  Created by Hwayeon on 2021/08/18.
//

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int lab[50][50] = {0, };
int copy_lab[50][50] = {0, };

//선택한 M개의 바이러스 위치를 담는 벡터
vector<pair<int, int>> virus;
//현재 시간에 활성화된 바이러스를 담는 벡터
vector<pair<int, int>> v;
//현재 시간에 복제된 바이러스를 담는 벡터
vector<pair<int, int>> nv;

//0-상, 1-하, 2-좌, 3-우
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

//모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간
int min_sec = -1;

//바이러스를 퍼뜨릴 수 있는 모든 칸의 개수
int max_virus = 0;
//처음 바이러스의 개수
int v_cnt = 0;

void copy_laboratory(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            copy_lab[i][j] = lab[i][j];
        }
    }
}

//BFS - 바이러스 퍼뜨리기
void spread_virus(){
    int sec = 0;
    //copy_lab에 처음 lab 상태를 넣어준다
    copy_laboratory();
    queue<vector<pair<int, int>>> q;
    //선택한 M개의 바이러스를 큐에 담아준다
    q.push(virus);
    //선택한 M개의 바이러스를 활성 상태(3)로 바꾼다
    for(int i=0; i<q.front().size(); i++){
        copy_lab[q.front()[i].second][q.front()[i].first] = 3;
    }
    //처음 바이러스의 개수로 cnt를 초기화
    int cnt = v_cnt;

    int x, y, nx, ny;
    //모든 빈 칸에 바이러스가 퍼진다면 ck = true
    bool ck = false;
    while(!q.empty()){
        v.clear();
        nv.clear();
        //현재 시간에 바이러스가 모든 빈 칸에 퍼졌다면, ck = true로 바꾸고 반복문을 종료한다
        if(cnt == max_virus){
            ck = true;
            break;
        }
        //현재 시간에 활성화된 바이러스의 위치를 담은 벡터 v
        v = q.front();
        q.pop();
        for(int i=0; i<v.size(); i++){
            x = v[i].first;
            y = v[i].second;
            //인접한 칸을 탐색
            for(int d=0; d<4; d++){
                nx = x+dx[d];
                ny = y+dy[d];
                //연구실을 벗어난 위치인 경우, continue
                if(nx<0 || nx>=N || ny<0 || ny>=N) continue;
                //비활성 상태의 바이러스인 경우, 활성화 상태로 바꿔주고 nv벡터에 담아준다
                if(copy_lab[ny][nx] == 2){
                    copy_lab[ny][nx] = 3;
                    nv.push_back({nx, ny});
                }
                //빈 칸인 경우, 활성화 상태로 바꿔주고 nv벡터에 담아준다
                else if(copy_lab[ny][nx] == 0){
                    copy_lab[ny][nx] = 3;
                    nv.push_back({nx, ny});
                    //새롭게 퍼진 바이러스이므로 cnt 카운팅
                    cnt ++;
                }
            }
        }
        //새로 활성화 된 바이러스가 있는 경우, 큐에 담는다
        if(nv.size() > 0) q.push(nv);
        sec++;
    }
    //모든 칸에 바이러스가 퍼진 경우, 최소 시간을 갱신한다
    if(ck){
        if(min_sec == -1) min_sec = sec;
        else if(sec < min_sec) min_sec = sec;
    }
}

//DFS - M개의 바이러스를 선택하는 조합
void select_virus(int x, int y){
	//M개의 바이러스를 선택한 경우
    if(virus.size() == M){
    	//바이러스를 퍼뜨린다
        spread_virus();
        return;
    }
    //중복되지 않게 바이러스 M개를 뽑는 경우의 수를 구한다
    for(int i=y; i<N; i++){
        if(i > y) x = 0;
        for(int j=x; j<N; j++){
            if(lab[i][j] == 2){
                virus.push_back({j, i});
                select_virus(j+1, i);
                virus.pop_back();
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> lab[i][j];
            //바이러스인 경우
            if(lab[i][j] == 2){
                v_cnt++;
                max_virus++;
            }
            //빈 칸인 경우
            else if(lab[i][j] == 0) max_virus++;
        }
    }
    //처음에 바이러스가 이미 모든 칸에 퍼져있는 경우, 0초
    if(v_cnt == max_virus){
        cout << 0 << endl;
    }
    else{
        select_virus(0, 0);
        cout << min_sec << endl;
    }
    return 0;
}
//시간복잡도 = O(N^2), 공간복잡도 = O(N^2)

728x90