[삼성SW역량테스트/DFS] 14503 로봇 청소기

삼성 문제들은 DFS문제가 많은것 같다. 3문제를 풀었는데 모두다 DFS문제였음.. 보니까 실제 자기네 회사에 들어갈만한 알고리즘에 대한 문제를 내는것 같음 

이 로봇 청소기 문제 같이 문제 내는 스타일이 실생활과 매우 밀접한 연관이 있음.

이 알고리즘이 실제로 로봇 청소기 안에 알고리즘으로 들어갈듯함

풀이 방법

로봇이 왼쪽으로 회전한다음 앞으로 갈수 있으면 그곳을 방문해서 그곳을 청소함.

따라서 방문 순서를 상 좌 하 우 순서로 잡아서 탐색을 진행해 나가야 한다.

만약에 현재 내가 위쪽을 바라 보고 있는데, 위쪽, 왼쪽 아래쪽,오른쪽 모두 청소를 했거나 벽으로 막혀있는데, 처음 바라보고있던 위치인 위쪽의 반대편 방향 즉 아래쪽 방향으로 로봇이 문워크 하듯이 현재 바라보고있는 방향 그대로 유지한채 뒤로만 움직인다.

근데 만약에 네방향 모두로 이동할수 없는데, 바라보고있는 반대방향으로 문워크도 불가능하게 되면 탐색을 중지한다.

다시 말해서, 집안을 모두 청소하지 못하는 경우가 발생할수 있다. 그래도 최대한으로 청소할수 있긴함.

0 1 2 3 에 각각 상 좌 하 우 가 맵핑 되어 있다.

코드

#include <iostream>

#include <algorithm>

using namespace std;

int plusX[4] = {-1,0,1,0};

int plusY[4] = {0,-1,0,1}; //상 좌 하 우 순서로 돌아감

int n,m;

int map[51][51];

int result;

void DFS(int x,int y,int d){ //d는 방향

    if(!map[x][y]){

        result++;

        map[x][y] = 2; //2는 그 지점을 방문했다는 의미

    }

//    cout<<endl;

//    printf("(%d,%d)방문함, %d쪽 방향 보는중 \n",x,y,d);

//    for(int i=0; i<n; i++){

//        for(int j=0; j<m; j++){

//            cout<<map[i][j]<<" ";

//        }

//        cout<<endl;

//    }

//    

    int i;

    for(i=d+1; i<d+5; i++)

    {

        int nextX = x+plusX[i%4];

        int nextY = y+plusY[i%4];

        if(nextX>=0 && nextX<n && nextY>=0 && nextY<m){

            if(!map[nextX][nextY])

                DFS(nextX,nextY,i%4);

        }

    }

        //네 방향 모두에 0이 없는 경우 -> 로봇이 상하좌우를 모두 청소했거나 벽으로 막혀있는경우

        int xx = x+plusX[(d+2)%4];

        int yy = y+plusY[(d+2)%4];

        if(map[xx][yy] == 2)

            DFS(xx,yy,d%4);

        else if(map[xx][yy] == 1){

            cout<<result<<endl;

            exit(0);

        }

    

}

int main(){

    cin>>n>>m;

    

    int r,c,d;

    cin>>r>>c>>d;

    

    if(d==3){

        d = 1;

    }

    else if(d==1){

        d = 3;

    }

    

    for(int i=0; i<n; i++)

        for(int j=0; j<m; j++)

            cin>>map[i][j];

    

    DFS(r,c,d);

    

    cout<<result<<endl;

    return 0;

}