[백준] 14503번: 로봇 청소기 (C++)

 

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

문제를 읽었을 때 많이 복잡해 보였는데 생각보다 간단하게 풀렸다.

주어진 조건 그대로 작성하였다.

 

북 : 0, 동 : 1, 남 : 2, 서: 3

 

rot 배열의 index는 현재 바라 보는 방향이고, 배열 값을 현재 좌표에 각각 더하면 왼쪽 좌표이다.

• ex) 북쪽(index = 0) 일 때  (x+ rot[0][0], y + rot[0][1])은 지금 북쪽을 바라봤을 때 왼쪽 좌표 (r, c)

back 배열의 index는 현재 바라보는 방향이고, 배열 값을 현재 좌표에 각각 더하면 한 칸 후진했을 때 좌표이다.

• ex) 북쪽(index = 0) 일 때  (x + back[0][0], y + back[0][1])은 북쪽을 바라보며 후진했을 때 좌표 (r, c)

nxt 배열의 index는 현재 바라보는 방향이고, 배열 값은 왼쪽으로 이동후 바라볼 방향이다.

• ex) 북쪽(index = 0)일 때 왼쪽으로 이동후 바라볼 방향은 3(서쪽)

왼쪽이 청소가 안되었고, 벽이 아니면 재귀적으로 들어가서 청소한다.

 

왼쪽이 청소가 되었거나 벽이면 다음 방향으로 회전하고 다음 왼쪽을 탐색한다. cnt++을 해준다.

 

4방향을 모두 탐색했을 때 (cnt == 4), 후진이 가능하면 후진을 하고 cnt = 0으로 초기화시킨다.

그리고 2번으로 돌아가서 4방향을 다시 탐색한다.

 

만약 후진을 못하면 break로 탈출하여 종료한다.

 

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;

int n, m, r, c, d, result;
int g[50][50];
int isClear[50][50];
// {북, 동, 남, 서}
int rot[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
int back[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
int nxt[4] = {3, 0, 1, 2};

int sol(int x, int y, int d) {
    isClear[x][y] = 1;
    result++;

    int cnt = 0;
    while (1) {       
        int nx = x + rot[d][0]; 
        int ny = y + rot[d][1];

        // 왼쪽좌표 확인
        if (!g[nx][ny] && !isClear[nx][ny]) return sol(nx, ny, nxt[d]);
        
        d = nxt[d]; // 다음 방향으로 회전
        cnt++;
         
         if (cnt != 4) continue;
         if (g[x + back[d][0]][y + back[d][1]]) break; // 후진 못하면

         x += back[d][0];
         y += back[d][1];
         cnt = 0;
    }
    return result;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> r >> c >> d;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    cout << sol(r, c, d);
    return 0;
}