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

문제

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

 

 

풀이

 벽 3개를 세울 수 있는 모든 조합에 대해 바이러스를 퍼뜨리고, 안전 영역의 수를 count 하여 최대 안정 영역의 수를 구하면 된다.

 

 나는 완전탐색 + BFS 로 구현하였다. 

 위의 아이디어를 코드로 구현하면 되고, 자세한 구현 방식은 코드의 주석을 참고하면 된다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Idx{
    int y, x;
};

int n, m, M; // n, m , 최댓값 M(=최대 영역)
int arr[8][8]; // 연수소 입력 정보
int visited[8][8]; // BFS 시 방문 표시
vector<Idx> v; // 벽을 세울 수 있는 공간(=0) 저장 벡터. 

// 바이러스 이동 방법
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

// w1, w2, w3에 벽을 세우고 바이러스가 퍼진 후의 안전영역 count 하는 함수
int BFS(int w1, int w2, int w3){
    int ans = 0;
    Idx wall1 = v[w1]; // 첫번째 벽
    Idx wall2 = v[w2]; // 두번째 벽
    Idx wall3 = v[w3]; // 세번째 벽
    
    queue<Idx> q;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(arr[i][j] == 2){
                // 바이러스 위치를 큐에 삽입
                q.push({i,j});
                
                // 방문 표시
                visited[i][j] = 1;
            }
            
            // 처음 안전 영역의 수를 count
            else if(arr[i][j] == 0){
                // 처음 안전 영역의 개수를 증가
                ans++;
            }
        }
    }
    
    // 추가로 세운 3개의 벽의 개수를 안전 영역에서 제외(벽에 세워진 공간은 안전 영역에서 제외)
    ans-=3;
    
    // BFS
    while(!q.empty()){
        Idx cur = q.front();
        q.pop();
        
        // 현재 바이러스 위치에서 바이러스 확산.
        for(int i=0; i<4; i++){
        
        	// 다음 위치
            int ny = cur.y+dy[i];
            int nx = cur.x+dx[i];
            
            // 배열 범위를 벗어난 경우 
            if(ny<0 || nx<0 || ny>=n || nx>=m) continue;
            
            // 이미 방문한 곳인 경우 
            if(visited[ny][nx] == 1) continue;
            
            // 벽이 세워져 있는 곳인 경우
            if(arr[ny][nx] == 1 || (ny ==wall1.y && nx==wall1.x) 
            ||(ny ==wall2.y && nx==wall2.x) || (ny ==wall3.y && nx==wall3.x)){
                continue;
            }
            
            // 바이러스가 퍼질 수 있는 경우, 바이러스 퍼뜨리고 안전 영역 수 감소
            q.push({ny,nx});
            visited[ny][nx] = 1;
            ans--;
        }
    }
    
    // visited 배열 초기화
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) visited[i][j] = 0;
    }
    
    // 최종 안전 영역 개수 반환 
    return ans;
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> arr[i][j];
            
            // 벽을 세울 수 있는 공간을 vector에 저장
            if(arr[i][j] == 0){
                v.push_back({i,j});
            }
        }
    }
    
    // 가능한 모든 조합에 대한 벽 세우기 진행
    for(int i=0; i<v.size();i++){
        for(int j=i+1; j<v.size(); j++){
            for(int k=j+1; k<v.size();k++){
                int ans = BFS(i,j,k);
                if(ans > M) M = ans;
            }
        }
    }
    
    cout << M << "\n";
    return 0;
}