[백준] 14504 - 로봇청소기 (C++)

문제 출처 :

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

문제 풀이:

jinu0418.tistory.com/43

[백준] 14504 - 로봇청소기 (Python)

• python 풀이와 같은 로직으로 풀었다.
• 역시나 C++ 답게 속도면에서 월등히 빠르다. python으로 푼 경우 pypy3을 이용해서 제출햇을때도 메모리가 121800KB , 시간 156m 가 소요되었는데 C++의 경우 2016KB, 0ms로 풀렸다.

#include <iostream>

using namespace std;

void print_map(int map[51][51],int n,int m)
{
    for(int i=0;i<n;i++)
    {
        for(int j =0; j<m;j++)
        {
            cout << map[i][j]<<" ";
        }
        cout <<"\n";
    }

}

int main(){
    int n,m;
    int r,c,d;
    int map[51][51];

    int ans =0;

    int dr[4] ={-1,0,1,0};
    int dc[4] ={0,1,0,-1};
    int turn_dir[4] = {3,0,1,2};

    int check_cnt =0;

    cin >> n>>m;
    cin >> r>>c>>d;

    for(int i=0;i<n;i++)
    {
        for(int j =0; j<m;j++)
        {
            int temp=0;
            cin >>temp;
            map[i][j]=temp;
        }
    }
    //print_map(map,n,m);

    int nd,nr,nc;
    int back_r,back_c;

    while(true){
        //현재 위치가 청소되어있지 않으면 청소하기
        if(map[r][c]==0) {
            map[r][c] = 9;
            ans++;
        }

        //방향 바꿔서 탐색 시작
        nd = turn_dir[d];
        nr = r + dr[nd];
        nc = c + dc[nd];

        //맵 범위내에 존재해야함
        if(nr<0 || nr>=n || nc<0 || nc>=m)
        {
            check_cnt++;
            d = nd;
        }
        else
        {
            //갈 위치가 청소 할 수 있는 경우
            if(map[nr][nc]==0)
            {
                r= nr;
                c= nc;
                d= nd;
                //해당 위치로 이동하고 청소
                map[nr][nc]=9;
                ans++;
                check_cnt=0;
            }
            else
            {
                d=nd;
                check_cnt++;
            }
        }
        if(check_cnt==4) {
            //4방향이 모두 안되는 경우
            back_r = r - dr[d];
            back_c = c - dc[d];
            if (back_r < 0 || back_r >= n || back_c < 0 || back_c >= m || map[back_r][back_c] == 1) {
                break;
            } else {
                r = back_r;
                c = back_c;
                check_cnt = 0;
            }
        }
    }
    cout << ans;

    return 0;
}