코테 노트/백준

백준 14502 연구소 C++

화요밍 2021. 1. 11. 19:19
728x90
반응형

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

최종 풀이

 

hwayeon351/BEAKJOON-Algorithms

백준 코딩테스트 풀이. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.

github.com

 

//
//  main.cpp
//  BJ14502
//
//  Created by 최화연 on 2022/04/02.
//

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int max_safe_num = 0;
int N, M;
int lab[8][8] = {0, };
int copy_lab[8][8] = {0, };
vector<pair<int, int>> virus;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void spread_virus(int sy, int sx) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if (copy_lab[ny][nx] == 0) {
                copy_lab[ny][nx] = 2;
                q.push({nx, ny});
            }
        }
    }
}

int get_safe_area() {
    int cnt = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if (copy_lab[i][j] == 0) {
                cnt ++;
            }
        }
    }
    return cnt;
}

void build_walls(int x, int y, int cnt) {
    if (cnt == 3) {
        memcpy(copy_lab, lab, sizeof(copy_lab));
        for(int i=0; i<virus.size(); i++) {
            spread_virus(virus[i].first, virus[i].second);
        }
        int safe_area = get_safe_area();
        if (safe_area > max_safe_num) max_safe_num = safe_area;
        return;
    }
    for(int i=y; i<N; i++) {
        if(i > y) x = 0;
        for(int j=x; j<M; j++) {
            if (lab[i][j] == 0) {
                lab[i][j] = 1;
                build_walls((j+1)%M, i, cnt+1);
                lab[i][j] = 0;
            }
        }
    }
}

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

풀이 과정

풀이 시간 28분

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int max_safe_num = 0;
int N, M;
int lab[8][8] = {0, };
int copy_lab[8][8] = {0, };
vector<pair<int, int>> virus;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

void spread_virus(int sy, int sx) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if (copy_lab[ny][nx] == 0) {
                copy_lab[ny][nx] = 2;
                q.push({nx, ny});
            }
        }
    }
}

int get_safe_area() {
    int cnt = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if (copy_lab[i][j] == 0) {
                cnt ++;
            }
        }
    }
    return cnt;
}

void build_walls(int x, int y, int cnt) {
    if (cnt == 3) {
        memcpy(copy_lab, lab, sizeof(copy_lab));
        for(int i=0; i<virus.size(); i++) {
            spread_virus(virus[i].first, virus[i].second);
        }
        int safe_area = get_safe_area();
        if (safe_area > max_safe_num) max_safe_num = safe_area;
        return;
    }
    for(int i=y; i<N; i++) {
        if(i > y) x = 0;
        for(int j=x; j<M; j++) {
            if (lab[i][j] == 0) {
                lab[i][j] = 1;
                build_walls((j+1)%M, i, cnt+1);
                lab[i][j] = 0;
            }
        }
    }
}

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

 

이전 풀이

풀이 시간 30분

 

풀이 1.

//
//  main.cpp
//  BJ14502
//
//  Created by Hwayeon on 2021/07/27.
//

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

int N, M;
int map[8][8] = {0,};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int cmp_map[8][8] = {0,};
int answer = 0;
vector<pair<int, int>> virus;

void copy_map(){
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cmp_map[i][j] = map[i][j];
        }
    }
}

void spread_virus(){
	//BFS 알고리즘 적용 -> O(V+E) = O(n^2)
	//바이러스의 위치들을 queue에 담아준다
    queue<pair<int, int>> q;
    for(int i=0; i<virus.size(); i++){
        q.push(virus[i]);
    }
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            //연구소를 벗어난 경우
            if(nx<0 || nx>=M || ny<0 || ny>=N) continue;
            //빈칸인 경우 바이러스를 퍼뜨린다
            if(cmp_map[ny][nx] == 0){
                cmp_map[ny][nx] = 2;
                q.push(make_pair(nx, ny));
            }
        }
    }
}

void count_safe_area(){
    int safe_area = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(cmp_map[i][j] == 0) safe_area++;
        }
    }
    if(answer < safe_area) answer = safe_area;
}

void build_wall(int cnt){
	//벽을 3개 설치한 경우, 바이러스를 퍼뜨린다
    if(cnt == 3){
        //퍼뜨리기 전 map의 상태를 보존하기 위해 cmp_map 배열에 복사하여 cmp_map에서 바이러스를 퍼뜨린다
        copy_map();
        spread_virus();
        //안전 영역의 크기를 구한다
        count_safe_area();
        return;
    }
    //벽을 설치한다
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(map[i][j] == 0){
                map[i][j] = 1;
                build_wall(cnt+1);
                map[i][j] = 0;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> map[i][j];
            if(map[i][j] == 2){
                virus.push_back(make_pair(j, i));
            }
        }
    }
    build_wall(0);
    cout << answer << endl;
    return 0;
}
#시간복잡도 = O(n^4), 공간복잡도 = O(n^2)

 

 

풀이 2.

풀이 시간  1시간 53분

//
//  main.cpp
//  BJ14502
//
//  Created by Hwayeon on 2021/01/09.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N,M;
int map[8][8] = {1,};
int map_copy[8][8] = {0,};
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int max_safe_area = 0;
struct location{
    int x;
    int y;
};
location loc;
vector<location> virus;

void spread_virus(){
    queue<location> q;
    int safe_area = 0;
    for(int i=0; i<virus.size(); i++){
        q.push(virus[i]);
    }
    while(!q.empty()){
        int v_x = q.front().x;
        int v_y = q.front().y;
        q.pop();
        for(int d=0; d<4; d++){
            int new_x = v_x+dx[d];
            int new_y = v_y+dy[d];
            if(new_x<0 || new_x>=N || new_y<0 || new_y>=M) continue;
            if(map_copy[new_x][new_y] == 0){
                map_copy[new_x][new_y] = 2;
                loc.x = new_x;
                loc.y = new_y;
                q.push(loc);
            }
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(map_copy[i][j]==0) safe_area++;
        }
    }
    if(safe_area > max_safe_area) max_safe_area = safe_area;
    return;
}

void install_wall(int wall){
    if(wall == 3){
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map_copy[i][j] = map[i][j];
            }
        }
        spread_virus();
        return;
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(map[i][j] == 0){
                map[i][j] = 1;
                install_wall(wall+1);
                map[i][j] = 0;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin >> map[i][j];
            if(map[i][j] == 0) continue;
            else if(map[i][j] == 2){
                loc.x = i;
                loc.y = j;
                virus.push_back(loc);
            }
        }
    }
    install_wall(0);
    cout << max_safe_area <<endl;
    
    return 0;
}

 

 이 문제는 DFS와 BFS를 활용하여 풀었다. DFS와 BFS에 대한 공부가 필요하다면 글 아래의 참고를 통해 공부하면 된다.

 

1. 바이러스 위치 저장

for(int i=0; i<N; i++){
	for(int j=0; j<M; j++){
    	cin >> map[i][j];
        if(map[i][j] == 0) continue;
        else if(map[i][j] == 2){
            loc.x = i;
            loc.y = j;
            virus.push_back(loc);
        }
    }
}

 입력값을 받아올 때, 현재 바이러스의 위치를 virus vector에 저장한다.

 

2. 벽 설치 DFS

void install_wall(int wall){
    if(wall == 3){
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map_copy[i][j] = map[i][j];
            }
        }
        spread_virus();
        return;
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(map[i][j] == 0){
                map[i][j] = 1;
                install_wall(wall+1);
                map[i][j] = 0;
            }
        }
    }
}

 벽이 3개가 설치된 후에 바이러스를 퍼뜨리기 위해 벽 설치를 재귀를 이용한 DFS로 구현했다.

map을 순서대로 탐색하여 빈 칸인 경우, 벽을 설치하고 재귀를 통해 다음 벽을 설치한다. 재귀 함수를 호출한 후에는 벽 3개를 설치하는 모든 경우의 수를 발생시키기 위해 다시 빈 칸으로 되돌려 놓는다.

이렇게 벽 3개가 설치되면, 바이러스를 퍼뜨린다. 이 때, map을 카피한 map_copy에 바이러스를 퍼뜨리도록 한다. (map의 원래 상태를 유지해야 다른 곳에 벽을 설치한 경우에 적용할 수 있다.)

 

3. 바이러스 퍼뜨리기 BFS

void spread_virus(){
    queue<location> q;
    int safe_area = 0;
    for(int i=0; i<virus.size(); i++){
        q.push(virus[i]);
    }
    while(!q.empty()){
        int v_x = q.front().x;
        int v_y = q.front().y;
        q.pop();
        for(int d=0; d<4; d++){
            int new_x = v_x+dx[d];
            int new_y = v_y+dy[d];
            if(new_x<0 || new_x>=N || new_y<0 || new_y>=M) continue;
            if(map_copy[new_x][new_y] == 0){
                map_copy[new_x][new_y] = 2;
                loc.x = new_x;
                loc.y = new_y;
                q.push(loc);
            }
        }
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(map_copy[i][j]==0) safe_area++;
        }
    }
    if(safe_area > max_safe_area) max_safe_area = safe_area;
    return;
}

 바이러스는 상,하,좌,우로 퍼지기 때문에 BFS를 활용했다.

1. 바이러스의 위치를 담아주는 q에 입력에서 저장한 최초 바이러스의 위치 vector virus를 담는다.

2. while 반복문

    1) q의 pop()하여 바이러스의 위치를 받아온다.

    2) 현재 바이러스의 위치에서 상, 하, 좌, 우를 탐색하여 빈 칸인 경우, 바이러스를 퍼뜨리고 q에 새로운 바이러스 위치를 추가한다.

    이 과정을 q가 empty일 때까지, 즉, 모든 바이러스를 퍼뜨릴 때까지 반복한다.

3. 안전 영역의 크기를 구하고 max_safe_area와 비교한다.

 

참고

 

BFS와 DFS

 BFS와 DFS는 가능한 모든 경우의 수를 탐색하는 완전 탐색 알고리즘이다. BFS는 Breadth-First Search로 너비 우선 탐색을 의미하고, DFS는 Depth-First Search로 깊이 우선 탐색을 의미한다. 설명 쉽게 설명.

hwayomingdlog.tistory.com

 

728x90
반응형

'코테 노트 > 백준' 카테고리의 다른 글

백준 13460 구슬 탈출 2 C++  (3) 2021.01.18
백준 14888 연산자 끼워넣기 C++  (0) 2021.01.17
백준 14890 경사로 C++  (0) 2021.01.14
백준 14503 로봇 청소기 C++  (0) 2021.01.11
백준 14889 스타트와 링크 C++  (0) 2021.01.06

'코테 노트/백준'의 다른글

  • 현재글백준 14502 연구소 C++

관련글

댓글

티스토리툴바