[백준/c++] 14502번: 연구소

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

14502번: 연구소

 

문제 요약

 

바이러스는 상하좌우 인접 빈칸으로 이동 가능

새로 세울 수 있는 벽의 개수 3개, 꼭 3개를 세워야 한다.

0 = 빈칸, 1 = 벽, 2 = 바이러스. 바이러스가 퍼질 수 없는 곳 = 안전 영역

안전 영역 크기의 최댓값을 구하라.

 

범위

 

세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8)

 

 

 

---

 

 

 

사실 여기서 완전 탐색을 사용해도 되는지 몰랐다. 완전 탐색으로 3개의 벽을 세우고 바이러스를 퍼트리고 안전영역을 수를 세면 된다.

일단, 연구소의 최대 크기가 8X8로 작아서 완전탐색으로 벽을 세 개씩 쌓아도 될 거 같다고 생각했다.

재귀 함수를 통해서 벽 세 개를 세우면 BFS를 통해서 바이러스를 퍼트려보자.

 

 

 

1. 벽 세우기 🧱

 

그동안 많이 연습했던 완전탐색(재귀호출)을 통해서 벽을 세웠다.

연구소를 쭉 돌면서 벽/바이러스 영역이 아닌 부분(0)을 찾으면 벽을 세우고 벽 카운트를 센다.(1, wall--)

그 후, 다시 재귀호출을 하는데 ➿ 앞서 세웠던 벽들은 고정되고 뒷부분의 벽들만 위치가 변경되기 때문이다!

만약 뒷 벽들도 모두 세워졌다면 그 앞의 벽들의 위치를 변경-고정하고 다시 뒷부분의 벽들의 위치를 변경하게 된다.

3개의 벽을 모두 세웠다면 변경된 연구소 구조를 복사해서 다른 배열에 복사한다(lab → tmp) [다른 위치에 배치된 벽들의 연구소도 탐색해야 하므로]

 

void solution(){
    //1. 벽세우기(완전탐색)
    if(wall == 0) {
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) tmp[i][j] = lab[i][j]; //벽을 세운 연구소를 복사해서 탐색
        return BFS();
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(lab[i][j] == 0){ //아무것도 없는 곳
                lab[i][j] = 1;  //벽 세우기
                wall--;
                solution();     //재귀호출 -> 앞의 벽들은 고정되고 뒤의 벽의 위치만 변경된다.
                wall++;         //초기화
                lab[i][j] = 0;  //초기화
            }
        }
    }
}

 

 

2. 바이러스 퍼트리기 🦠

 

입력받으면서 바이러스(2) 영역을 따로 벡터(virus)에 넣어줬는데, 이는 BFS를 변하게 하기 위해서였다. ➿바이러스의 시작점들을 넣어준 것이다. 이렇게 하면 따로 바이러스의 시작점을 반복문을 통해 찾지 않아도 된다. 이를 큐에 넣어주고 탐색을 시작한다.

x와 y에 바이러스의 시작점을 넣고, 방향에 대한 정보를 넣은 배열 dir를 통해 상하좌우로 이동한다. 이때 꼭 확인할 것들이 있다.

 

 - 영역 내에 있는지 확인하기

 - 빈 영역인지 확인하기 (아니면 바이러스를 퍼트릴 수 없으니)

 

위의 두 가지 조건에 만족한다면 해당 위치를 q에 넣어주고 바이러스 오염 영역(2)으로 변경해준다.

 

void BFS(){
    //2. 바이러스 퍼트리기
    queue<pair<int, int>> q;
    for(int i=0; i<virus.size(); i++) q.push(make_pair(virus[i].first, virus[i].second));
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 1 || dy < 1 || dx > n || dy > m) continue; //영역 내인지 확인
            if(tmp[dx][dy] != 0) continue;                     //벽/바이러스 영역이면 패스
            q.push(make_pair(dx, dy));
            tmp[dx][dy] = 2;                                   //바이러스 전염!
        }
    }
    
    // ...

}

 

 

3. 안전 영역 카운트 ✅

 

바이러스를 퍼트릴 수 있는 모든 공간을 돌았다면 큐가 빌 것이다. 그 후엔 안전 영역을 카운트해주면 된다. ➿ 0 인 영역을 카운팅

가장 큰 값을 찾아야 하므로 answer를 업데이트해준다.

 

void BFS(){

    //...

    //3. 안전영역카운트
    int cnt=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(tmp[i][j] == 0) cnt++;
        }
    }
    ans = cnt > ans ? cnt : ans; //가장 큰 값 찾아야 하므로 ans update
}

 

 

 

 

---

 

 

 

전체 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
bool visited[10][10] = {false};
vector<pair<int, int>> virus;
int n, m, wall = 3, ans=0, lab[10][10], tmp[10][10], dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

void input(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> lab[i][j];
            if(lab[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
}

void BFS(){
    queue<pair<int, int>> q;
    for(int i=0; i<virus.size(); i++) q.push(make_pair(virus[i].first, virus[i].second));
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i=0; i<4; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 1 || dy < 1 || dx > n || dy > m) continue; 
            if(tmp[dx][dy] != 0) continue;                     
            q.push(make_pair(dx, dy));
            tmp[dx][dy] = 2;                                   
        }
    }
    
    int cnt=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(tmp[i][j] == 0) cnt++;
        }
    }
    ans = cnt > ans ? cnt : ans;
}

void solution(){
    if(wall == 0) {
        for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) tmp[i][j] = lab[i][j]; 
        return BFS();
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(lab[i][j] == 0){ 
                lab[i][j] = 1; 
                wall--;
                solution();    
                wall++;        
                lab[i][j] = 0; 
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    cout << ans << '\n';
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!