[백준] 14503.로봇 청소기

[풀이 1]

 

처음에 시뮬레이션인줄 알고 조건 하나씩 다 따지면서 아래와 같이 구현

#include <iostream>

using namespace std;

//0: 빈칸, 1:벽

int N,M;
int map[50][50];
int dir;
int x,y;
int cnt=0; // number of clean space by robot

//0:북 , 1:동, 2:남, 3:서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int main(void)
{
    
    cin >> N >> M ;
    cin >> x >> y >> dir;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    while(1){
        
        if(map[x][y]==0){
            map[x][y]=2; //현재 위치 청소
            cnt++;
        }
        
        int pdir = dir;
        
        for(int i=0;i<4;i++){
            //왼쪽으로 회전
            if(dir == 0)    dir = 3;
            else    dir-=1;
            
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if(map[nx][ny]==0){ //왼쪽으로 회전했을 때, 청소할 공간이 존재하는 경우
                x = nx; y= ny;
                break;
            }
        }
        
        if(pdir == dir && map[x][y] != 0 ) //후진하는 경우
        {
            x =x-dx[dir];
            y =y-dy[dir];
        }
        
        if(map[x][y] == 1)  break; // 후진했는데 벽인 경우
        
            }
    
    cout << cnt;
    return 0;
    
}

 

[풀이 2]

 

맞았습니다가 나왔지만 구글링을 해보니 DFS를 사용하여 재귀함수로 풀 수 있다는 것을 아래와 같이 재귀함수를 사용해서 풀어봤다.

 

 

#include <iostream>

using namespace std;

//0: 빈칸, 1:벽

int N,M;
int map[50][50];
int cnt=0; // number of clean space by robot

//0:북 , 1:동, 2:남, 3:서
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};


void DFS(int x , int y, int dir){
    
    map[x][y]=2;

    for(int i=0;i<4;i++){
        
        if(dir == 0)    dir = 3;
        else    dir-=1;
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(map[nx][ny]==0){
            DFS(nx,ny,dir);
            return;
        }
    }
    /* 후진 하는 경우 */
    x-=dx[dir];
    y-=dy[dir];
    if(map[x][y]==1)    return;
    else    DFS(x,y,dir);

}
int main(void)
{
    int x,y,dir;
    
    cin >> N >> M ;
    cin >> x >> y >> dir;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            cin >> map[i][j];
    }
    
    DFS(x,y,dir);
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            if(map[i][j]==2)    cnt++;
    }
    cout << cnt;
    return 0;
    
}

 

재귀함수를 사용하여 후진 부분에서 시뮬레이션보다 훨씬 간단하게 풀 수 있었다.

 

조언, 질문 환영입니다!

댓글 남겨주세요~