[Baekjoon] 삼성 sw 역량 테스트(연구소)

• 이 문제는 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

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

int result=0;       // 최댓값
int n,m;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};      // 상하좌우

// 사각형 안에 있는지 판단하는 함수
bool inside(int y,int x){
    return 0<=y && y<n && 0<=x && x<m;
}

// 벽 3개를 세우기 전까지는 백트래킹 기법으로 탐색
// 3개를 세울 시 dfs로 바이러스를 퍼뜨린 후 check배열로 퍼진곳 표시
// 안전한 곳(0)이면서 바이러스가 퍼지지 않은 곳 표시
void dfs(int arr[8][8],int y,int x,int len,int cnt){
    if(len==cnt){
        int count=0;
        int check[8][8]={0};
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]==2){
                    queue<pair<int,int>> q;
                    q.push(make_pair(i,j));
                    while(!q.empty()){
                        pair<int,int> p=q.front();
                        int a=p.first;
                        int b=p.second;
                        q.pop();
                        for(int k=0;k<4;k++){
                            int da=a+dir[k][0];
                            int db=b+dir[k][1];
                            
                            if(inside(da,db)){
                                if(arr[da][db]==0 && !check[da][db]){
                                    q.push(make_pair(da,db));
                                    check[da][db]=1;
                                }
                            }
                        }
                    }
                }
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]==0 && check[i][j]==0){
                    count++;
                }
            }
        }
        if(count>result){
            result=count;
        }
    }
    else{
        for(int i=y;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]==0){
                    arr[i][j]=1;
                    dfs(arr,i,j,len,cnt+1);
                    arr[i][j]=0;
                }
            }
        }
    }
}


int main(){
    
    cin>>n>>m;
    int arr[8][8];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    dfs(arr,0,0,3,0);
    
    cout<<result;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.