백준 14503: 로봇 청소기

문제

문제 링크: https://www.acmicpc.net/problem/14503

처음에는 재귀를 이용해서 풀려고 했었지만, 실력부족으로 인하여 while문을 사용해서 움직였습니다.

처음에 주어진 입력으로 로봇 움직임을 보려고 개 뻘짓도 해보고... 엑셀에 그려가면서 하나하나 체크 했던것 같습니다.

DFS문제들만 풀면 무한 루프에 빠지는게 대다수였던것 같고 이 문제 또한 그랬습니다... ㅠㅠ

엑셀에 그려가면서 했던것입니다.. 다 못할꺼 같아서 무한 루프가 생겼던 점까지 해보았습니다. 

문제가 2-3 조건에서 뒤로 갔을때, 이미 체크 되어있는 것을 생각을 못하는 정말 바보같은 실수를 했습니다.

가로 안은 로봇이 움직이는 순서입니다. 방향은 해당 위치에서 턴 할때마다 적어 놓았습니다.

움직일 방향 배열의 순서도 북, 동, 남, 서로 했습니다. 

그 이유는 다음 청소할 위치를 검사할때, 지정된 방향 값으로 배열 인덱스와 맞추기 위해서 입니다.

코드

#include <cstdio>
 
using namespace std;
 
int map[50][50];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};  //북 동 남 서
int n,m,r,c,d;
 
int turn(int d){
    if(d==0) return 3;
    else if(d==1) return 0;
    else if(d==2) return 1;
    else return 2;
}
void clean(){
    int ans = 0;    //청소한 구역 개수
    int num = 0;    //4방향 모두 청소할 수 없는 경우를 확인
    //처음 위치 청소
    map[r][c] = 2;
    ans++;
    while(1){
        if(num > 3){
            //뒤로 돌기
            int nd = turn(turn(d));
            int nr = r + dr[nd];
            int nc = c + dc[nd];
            //기존 방향으로 다시 돌기
            nd = turn(turn(nd));
            if(0<=nr && nr<n && 0<=nc && nc<m){
                if(map[nr][nc] == 0){
                    map[nr][nc] = 2;
                    ans++;
                    num = 0;
                    r = nr;
                    c = nc;
                    d = nd;
                }
                else if(map[nr][nc] == 2){
                    num = 0;
                    r = nr;
                    c = nc;
                    d = nd;
                }
                else if(map[nr][nc] == 1){
                    printf("%d\n",ans);
                    return;
                }
            }
        }
        int nd = turn(d);
        int nr = r + dr[nd];
        int nc = c + dc[nd];
            
        if(0<=nr && nr<n && 0<=nc && nc<m){
            if(map[nr][nc] == 0){
                map[nr][nc] = 2;
                ans++;
                num = 0;
                r = nr;
                c = nc;
                d = nd;
            }
            //벽 혹은 이미 청소한 경우 회전만하며 왼쪽 확인.
            else{
                num++;
                d = nd;
            }
        }
    }
    printf("%d\n", ans);
}
 
int main(){
    scanf("%d %d", &n, &m);
    scanf("%d %d %d", &r, &c, &d);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d",&map[i][j]);
        }
    }
    clean();
    return 0;
}