[백준/c++] 14503번: 로봇 청소기

 

 

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

가장 헷갈리는 게 BFS, DFS 어떤 걸로 할지 결정하는 것 같다.. 뭔가 BFS 같은데 DFS인..

근데 문제를 다시 보면 DFS로 해야 한다. 로봇청소기가 여러 곳으로 넓게 퍼지면서 이동하는 게 아니라 청소 안 한 곳만 바라보면서 계속 들어가기 때문에,, 처음에 BFS로 했다가 뭔가 안풀려서 DFS로 방향을 틀었다. 미리 알았다면 좋았을 텐데...^^

문제를 읽어보면 조건들이 많은데, 이 조건들을 순서대로 쭉 구현해주면 된다.

 

---

 

1. 현재 위치를 청소하고, (이때, bool 배열을 사용하지 않고 그냥 2로 변경해줬다) 청소 카운팅++

 

2. 왼쪽으로 회전하면서 방 범위를 벗어나거나 벽인 경우 그냥 넘어가기

    빈 공간이면(청소 안 함) DFS로 들어가기

 

3. 여기서 DFS에 들어가지 않았다면 네 방향 모두 청소한 곳 or 청소하지 못하는 곳 이므로 후진하도록 위치 값 설정하기

    1. 벽이라면 청소 카운팅 출력하고 바로 종료. 여기서 exit(0)가 아니라 return으로 한다면 이 재귀 함수가 빠져나가면서

        계속 청소 카운팅을 출력하므로 꼭 exit(0)으로 바로 종료시켜줘야 한다.

    2. 벽이 아니면 후진한 위치로 DFS 들어가기 (이때, 이전 방향 바꾸면 안 됨~ 후진은 방향 유지하면서 뒤로 이동하는 것이므로)

 

 

여기서, 배열 회전하는 것은 좌측으로만 회전하기 때문에, 

좌측 회전 방향을 저장하는 dd는 (4+(d-i))%4로 해줬다.

후진의 경우, 방향을 바꾸지 않지만 뒤로 가는 것이므로 +2 인덱스를 해주면 된다!.

대신 0->2는 +2 지만 2->0는 +2로 안되므로 (d+2)%4로 해서 4%4 = 0으로 간편하게 해 줄 수 있다~

 

 

✨ 외워두면 좋은...

 

 - 좌측 회전 (n+(cur-i))% n

 - 우측 회전 (cur+i)% n

 

 

#include <iostream>
#include <queue>
#define MAX 52
using namespace std;
int room[MAX][MAX], n, m, clean_cnt=0;
int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}}; //북, 동, 남, 서

void DFS(int x, int y, int d){
    //빈공간인지 체크
    if(room[x][y] == 0){
        room[x][y] = 2; //청소 표시!
        clean_cnt++;
    }
    
    for(int i=1; i<=4; i++){
        int dd = (4+(d-i))%4;
        int dx = x + dir[dd][0];
        int dy = y + dir[dd][1];
        
        if(dx<0||dy<0||dx>=n||dy>=m||room[dx][dy]==1) continue; //범위 벗어나거나 벽이면 패스
        
        if(room[dx][dy] == 0) DFS(dx, dy, dd);
    }
    
    //여기 온거면 네 방향 모두 청소한 상태!
    //후진할 수 있는지 보고 할 수 있으면 DFS 계속 ㄱㄱ
    //벽이면 후진 못하므로 카운팅 출력하고 끝
    int bd = (d+2)%4;
    int bx = x + dir[bd][0];
    int by = y + dir[bd][1];
    
    if(room[bx][by] == 1){
        cout << clean_cnt << '\n';
        exit(0); //바로 종료!
    }
    DFS(bx, by, d);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    int x, y, d;
    cin >> x >> y >> d;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> room[i][j];
    DFS(x, y, d);
    return 0;
}

 

역시 DFS가 코드가 깔끔하고 좋은 것 같다.. 근데,, BFS 문제가 더 많은 듯..ㅎ..