백준 14503번 - 로봇 청소기

백준 14503번 - 로봇 청소기

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

14503번: 로봇 청소기

이 문제는 시뮬레이션 문제이다.

처음 문제를 봤을 때

"왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다."

이 문장을 보고 해당 칸의 왼쪽 방향에 있는 모든 칸들을 확인해야 하는 문제로 착각했다.

(솔직히 문제가 오해의 소지가 있게 보이긴 했음ㅠ)

그렇게 해서 함수로 전부 확인하고 예제를 돌려보니 답이 안 나오네..

결국 질문 검색 판을 읽다가 위치한 칸의 바라보는 방향의 왼쪽 칸 하나만 확인하면 된다는 것을 알았다.

코드가 100줄 가까이 되었었는데 너무 화가 나네..

 

쨌든 이 문제의 핵심은 바라보는 방향인 것 같다.

조건 2-c에서 보면

"네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다."

이 조건의 바라보는 방향은 처음의 바라보는 방향, 즉 해당 칸에 도착했을 때의 방향이다.

 

문제를 해결할 때 방법이 두 가지가 생각났는데

첫 번째는 칸에 도착하자마자 4방향을 한 번에 검사 하기

두 번째는 한 방향씩 돌아가며 4번 검사하기였다.

 

나는 두 번째 방식으로 해결했는데 이유는 4번 검사를 하면 결국 다시 원상태로 돌아오기 때문에

바라보는 방향을 따로 저장해놓지 않아도 되기 때문이었다.

 

#include <iostream>
#pragma warning(disable:4996)
using namespace std;
 
int n, m, r, c, d;
int map[51][51];
int back_x[4] = { 1,0,-1,0 };
int back_y[4] = { 0,-1,0,1 };
int next_x[4] = { 0,-1,0,1 };
int next_y[4] = { -1,0,1,0 };
bool clean[51][51] = { false };
 
int change_d(int dir) {
    if (dir == 0)return 3;
    else if (dir == 1)return 0;
    else if (dir == 2)return 1;
    else return 2;
}
 
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]);
        }
    }
    int ans = 0;
    while (1) {
        /*왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
          왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.*/
        if (clean[r][c] == false) {
            clean[r][c] = true;  //청소가 되었으면 true;
            ans++;
        }
        bool stop = false;
        for (int i = 0; i < 4; i++) {
            if (map[r + next_x[d]][c + next_y[d]] == 1) { //갈 방향에 방해물이 있다면
                d = change_d(d);
                continue;
            }
            //청소가 되어 있는지 확인(현재 방향)
            bool flag = clean[r + next_x[d]][c + next_y[d]];
            if (flag == false) {    //청소할 공간이 남아 있다면
                r = r + next_x[d];
                c = c + next_y[d];
                d = change_d(d);
                stop = true;
                break;
            }
            else {
                d = change_d(d);
            }
        }
        /*네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
          네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.*/
        if (stop == false) {
            int a = r + back_x[d];
            int b = c + back_y[d];
            if (map[a][b] == 1) break;
            r = a; c = b;
        }
    }
    printf("%d\n", ans);
}

 

문제를 이해하는데 시간이 걸렸지만 막상 구현해 보면 어렵지 않은 문제였던 거 같다.