[C++][백준 14502] 연구소

[문제]

14502번: 연구소 (acmicpc.net)

14502번: 연구소

[문제 풀이]

n * m의 공간인 연구소에 바이러스가 퍼졌다. 2인 칸에서 부터 바이러스는 퍼지고 벽(1)의 부딪히거나 범위에 부딪히면 더 이상 퍼지지 못한다. 3개의 벽을 추가로 건설해서 바이러스를 최대한 덜 퍼트펴보자.

 

벽은 무조건 3개이고 0인 곳에 세울 수 있다.

그러니 0인 칸의 모든 좌표값을 알고 있을 때 이 중 3가지를 뽑아서 나올 수 있는 경우의 수가 문제에서 요구하는 거라고 봐도 무방할 것이다.

백준 n과 m 시리즈에서 자주 접했던 문제 즉, 0의 모든 좌표 (n) 에서 3개의 좌표(m)을 뽑아보자.

void backTrack(int cnt){

    if(loc.size() == 3){
        return;
    }

    for(int i = cnt;i<vec.size();i++){
        if(visited[vec[i].first][vec[i].second] == 0){
            visited[vec[i].first][vec[i].second] = 1;
            loc.push_back(vec[i]);
            backTrack(cnt + 1);
            loc.pop_back();
            visited[vec[i].first][vec[i].second] = 0;
        }
    }
    return;
}

 

중복좌표를 만들지 않기 위하여 visited 처리와 loc이라는 벡터에 해당 위치를 넣고 빼고를 반복하면서 백트래킹을 해주었다.

 

이제 loc의 크기가 3 즉, 3개의 벽이 설치되었다면 bfs를 이용해서 2가 총 몇번을 갈 수 있는지 파악을 하자.

 

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < m){
        return true;
    }
    return false;
}

int bfs(){

    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            viurs_visited[i][j] = 0;
        }
    }
    
    //answer는 0의 숫자를 세는 변수. oneNum은 이미 세워져있는 벽의 숫자.
    int answer = n * m - oneNum - 3;

    for(int i = 0;i<loc.size();i++){
        arr[loc[i].first][loc[i].second] = 1;
    }

    queue<pair<int,int> > q;
    for(int i = 0;i<virus.size();i++){
        q.push(virus[i]);
        viurs_visited[virus[i].first][virus[i].second] = 1;
        answer--;
    }

    while(q.size() > 0){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(inRange(nextX,nextY) == true && viurs_visited[nextX][nextY] == 0){
                //벽이 아니라면
                if(arr[nextX][nextY] == 0){
                    viurs_visited[nextX][nextY] = 1;
                    q.push(make_pair(nextX,nextY));
                    answer--;
                }
            }
        }
    }

    for(int i = 0;i<loc.size();i++){
        arr[loc[i].first][loc[i].second] = 0;
    }

    return answer;
}

 

이와 같은 bfs를 통해서 우리들은 0의 좌표를 알 수가 있다.

bfs + 백트래킹 문제가 처음이면 어려울만 하지만 골드5를 넘어서는 bfs의 경우에는 조건이 추가되어 있거나 bfs + 이분탐색, 백트래킹 등으로 조건을 주는 경우가 많다. 처음에는 어려울 수 있지만 풀다보면 익숙해지니 양치기를 해보자.

[회고]

테스트 케이스가 좋아서 특별히 어려운 점은 없었다.

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n,m;
int answer;
int oneNum;
int arr[10][10];
int visited[10][10];
int viurs_visited[10][10];
int max_answer;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<pair<int,int> > vec;
vector<pair<int,int> > loc;
vector<pair<int,int> > virus;

bool inRange(int x, int y){
    if(x >= 0 && x < n && y >= 0 && y < m){
        return true;
    }
    return false;
}

int bfs(){

    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            viurs_visited[i][j] = 0;
        }
    }

    int answer = n * m - oneNum - 3;

    for(int i = 0;i<loc.size();i++){
        arr[loc[i].first][loc[i].second] = 1;
    }

    queue<pair<int,int> > q;
    for(int i = 0;i<virus.size();i++){
        q.push(virus[i]);
        viurs_visited[virus[i].first][virus[i].second] = 1;
        answer--;
    }

    while(q.size() > 0){
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for(int i = 0;i<4;i++){
            int nextX = curX + dx[i];
            int nextY = curY + dy[i];
            if(inRange(nextX,nextY) == true && viurs_visited[nextX][nextY] == 0){
                //벽이 아니라면
                if(arr[nextX][nextY] == 0){
                    viurs_visited[nextX][nextY] = 1;
                    q.push(make_pair(nextX,nextY));
                    answer--;
                }
            }
        }
    }

    for(int i = 0;i<loc.size();i++){
        arr[loc[i].first][loc[i].second] = 0;
    }

    return answer;
}

void backTrack(int cnt){

    if(loc.size() == 3){
        if(max_answer < bfs()){
            max_answer = bfs();
        }
        return;
    }

    for(int i = cnt;i<vec.size();i++){
        if(visited[vec[i].first][vec[i].second] == 0){
            visited[vec[i].first][vec[i].second] = 1;
            loc.push_back(vec[i]);
            backTrack(cnt + 1);
            loc.pop_back();
            visited[vec[i].first][vec[i].second] = 0;
        }
    }
    return;
}

int main(){
    cin>>n>>m;

    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin>>arr[i][j];
            if(arr[i][j] == 0){
                vec.push_back(make_pair(i,j));
            }
            else if(arr[i][j] == 2){
                virus.push_back(make_pair(i,j));
            }
            else if(arr[i][j] == 1){
                oneNum++;
            }
        }
    }

    backTrack(0);
    cout<<max_answer<<endl;
    return 0;
}