[BaekJoon] 삼성 sw 역량 테스트(로봇 청소기)

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

문제

 

예시

 

풀이

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

int n,m;
int data[50][50];
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};      // 북 -> 서 -> 남 -> 동
                                                // 무조건 이 순서 (북에서 왼쪽 서 , 서에서 왼쪽 남)
// 좌표를 담는 구조체
struct node{
    int x;
    int y;
    node(int y,int x):y(y),x(x){}
};

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

int main(){
    
    int result=0;
    cin>>n>>m;
    
    int r,c,t;
    cin>>r>>c>>t;
    // 문제와 북서남동과 dir과 순서가 다르기 때문에 처음만 조정
    if(t==1 || t==3){t=(t+2)%4;}
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>data[i][j];
        }
    }
    
    
    int check[50][50]={0};
    queue<node> q;
    q.push(node(r,c));
    result++;
    check[r][c]=1;
    
    // dfs로 하되 청소가 안된 구역이 있으면 break
    while(1){
        int y=q.front().y;
        int x=q.front().x;
        q.pop();
        
        bool flag=false;
        for(int cnt=1;cnt<=4;cnt++){
            int d=(t+cnt)%4;            // 0-> 1, 1-> 2, 2->3 ,3-> 0 하기 위해 % 사용
            int dy=y+dir[d][0];
            int dx=x+dir[d][1];
            if(inside(dy,dx)){
                if(data[dy][dx]==0 && check[dy][dx]==0){    // 청소가 안된구역
                    flag=true;
                    q.push(node(dy,dx));
                    check[dy][dx]=1;
                    result++;
                    t=d;
                    break;
                }
            }
        }
        
        // 동서남북 모두 안될 경우 뒤로 후진 -> +2한 후 %4
        if(!flag){
            int d=(t+2)%4;
            int dy=y+dir[d][0];
            int dx=x+dir[d][1];
            
            if(inside(dy,dx)){
                if(data[dy][dx]!=1){
                    q.push(node(dy,dx));
                }
                else{break;}
            }
            else{
                break;
            }
        }
    }
    
    
    cout<<result;
}

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