[BaekJoon] 삼성 sw 역량 테스트(감시)

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

문제

 

예시

 

풀이

#include <iostream>
#include <algorithm>
using namespace std;


int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int result=987987987;
int n,m;
int arr[10][10];

bool inside(int y,int x){
    return 0<=y && y<n && 0<=x && x<m;
}

void dfs(int y,int x,int cost[10][10],bool check[10][10]){
    if(check[y][x] || arr[y][x]==0 || arr[y][x]==6){
        if(inside(y,x+1)){
            dfs(y,x+1,cost,check);
        }
        else{
            if(inside(y+1,0)){
                dfs(y+1,0,cost,check);
            }
            else{
                
                int finish[10][10]={0};
                
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        if(check[i][j]){
                            if(arr[i][j]==1){
                                int d=cost[i][j];
                                int dy=i+dir[d][0];
                                int dx=j+dir[d][1];
                                while(inside(dy,dx) && arr[dy][dx]!=6){
                                    finish[dy][dx]=1;
                                    dy+=dir[d][0];
                                    dx+=dir[d][1];
                                }
                            }
                            else if(arr[i][j]==2){
                                int f=cost[i][j];
                                for(int k=0;k<=2;k+=2){
                                    int d=(f+k)%4;
                                    int dy=i+dir[d][0];
                                    int dx=j+dir[d][1];
                                    while(inside(dy,dx) && arr[dy][dx]!=6){
                                        finish[dy][dx]=1;
                                        dy+=dir[d][0];
                                        dx+=dir[d][1];
                                    }
                                }
                            }
                            else if(arr[i][j]==3){
                                int f=cost[i][j];
                                for(int k=0;k<2;k++){
                                    int d=(f+k)%4;
                                    int dy=i+dir[d][0];
                                    int dx=j+dir[d][1];
                                    while(inside(dy,dx) && arr[dy][dx]!=6){
                                        finish[dy][dx]=1;
                                        dy+=dir[d][0];
                                        dx+=dir[d][1];
                                    }
                                }
                            }
                            else if(arr[i][j]==4){
                                int f=cost[i][j];
                                for(int k=0;k<3;k++){
                                    int d=(f+k)%4;
                                    int dy=i+dir[d][0];
                                    int dx=j+dir[d][1];
                                    while(inside(dy,dx) && arr[dy][dx]!=6){
                                        finish[dy][dx]=1;
                                        dy+=dir[d][0];
                                        dx+=dir[d][1];
                                    }
                                }
                            }
                            else{
                                int f=cost[i][j];
                                for(int k=0;k<4;k++){
                                    int d=(f+k)%4;
                                    int dy=i+dir[d][0];
                                    int dx=j+dir[d][1];
                                    while(inside(dy,dx) && arr[dy][dx]!=6){
                                        finish[dy][dx]=1;
                                        dy+=dir[d][0];
                                        dx+=dir[d][1];
                                    }
                                }
                            }
                        }
                    }
                }
                
                int cnt=0;
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        if(arr[i][j]==0 && finish[i][j]==0){
                            cnt++;
                        }
                    }
                }
                
                result=min(result,cnt);
            }
        }
    }
    else{
        if(1<=arr[y][x] && arr[y][x]<=5){
            if(arr[y][x]==1 || arr[y][x]==3 || arr[y][x]==4){
                for(int i=0;i<4;i++){
                    cost[y][x]=i;
                    check[y][x]=1;
                    dfs(y,x,cost,check);
                }
            }
            else if(arr[y][x]==2){
                for(int i=0;i<2;i++){
                    cost[y][x]=i;
                    check[y][x]=1;
                    dfs(y,x,cost,check);
                }
            }
            else{
                check[y][x]=1;
                dfs(y,x,cost,check);
            }
            check[y][x]=0;
        }
    }
}


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

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    
    bool check[10][10]={0};
    int cost[10][10]={0};
    dfs(0,0,cost,check);
    
    cout<<result;
}

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