[BOJ 14503 // C++] 로봇 청소기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1261번 문제인 알고스팟이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

이 문제는 N과 M의 크기가 작으므로, 문제의 주어진 조건을 충실히 구현하면 되는 문제이다.

다음과 같은 순서로 반복하게 코딩을 하면 이 문제에 주어진 조건을 성공적으로 구현할 수 있다.

 

[문제조건 1]

1) 현재 로봇청소기가 있는 칸을 청소한다(2를 기록).

 

[문제조건 2a, 2b]

2) 로봇청소기가 보는 방향의 왼쪽 칸이 청소가 안된 빈칸(0)인지 확인하고, 빈칸이라면 방향과 위치를 바꿔 기록한 뒤 1로 이동한다.

3) 로봇청소기가 보는 방향의 뒤쪽 칸이 청소가 안된 빈칸(0)인지 확인하고, 빈칸이라면 방향과 위치를 바꿔 기록한 뒤 1로 이동한다.

4) 로봇청소기가 보는 방향의 오른쪽 칸이 청소가 안된 빈칸(0)인지 확인하고, 빈칸이라면 방향과 위치를 바꿔 기록한 뒤 1로 이동한다.

5) 로봇청소기가 보는 방향의 앞쪽 칸이 청소가 안된 빈칸(0)인지 확인하고, 빈칸이라면 방향과 위치를 바꿔 기록한 뒤 1로 이동한다.

 

[문제조건 2c, 2d]

6) 여기까지 왔다면 로봇청소기의 사방은 청소할 필요가 없다. 로봇청소기가 보는 방향의 뒤쪽 칸이 청소가 된 빈칸(2)인지 확인하고, 청소가 된 칸이라면 위치만 바꿔 기록한 뒤 1로 이동한다.

7) 그렇지 않다면 반복문을 종료한다(로봇청소기의 작동을 멈춘다).

 

[답 출력]

8) 전체 영역에서 청소한 칸의 수(2의 개수)를 세어 출력한다.

 

 

이 알고리즘은 청소하는 영역의 크기가 유한하고, 로봇청소기가 같은 장소를 반복해서 움직이는 경우(사이클)가 존재하지 않는다는 것을 확인하자.

 

로봇 청소기가 앞뒤 방향만으로 움직이며 반복하는 경우가 없다는 것은 자명하다. 따라서 같은 장소를 반복해서 움직이는 경우가 있다면 로봇청소기가 왼쪽이나 꺾는 경우가 포함되어 있어야 한다. 그러나 로봇 청소기가 왼쪽 또는 오른쪽으로 꺾는 경우는 그 칸이 청소되어있지 않을 때 뿐이므로, 왼쪽 또는 오른쪽으로 꺾으면 영역에서 청소가 필요한 칸(0)의 개수가 하나 감소한다. 따라서 칸의 개수는 음수가 될 수 없으므로 로봇 청소기가 같은 장소를 반복해서 움직이는 일은 불가능하다.

 

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int map[51][51];
int robotx, roboty, robotd;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

bool leftchk() {
    int d = robotd - 1;
    if (d < 0) d += 4;
    int x = robotx + dx[d], y = roboty + dy[d];
    return (map[x][y] == 0) ? true : false;
}

bool rightchk() {
    int d = robotd + 1;
    if (d > 3) d -= 4;
    int x = robotx + dx[d], y = roboty + dy[d];
    return (map[x][y] == 0) ? true : false;
}

bool frontchk() {
    int d = robotd;
    int x = robotx + dx[d], y = roboty + dy[d];
    return (map[x][y] == 0) ? true : false;
}

bool backchk1() {
    int d = robotd;
    int x = robotx - dx[d], y = roboty - dy[d];
    return (map[x][y] == 0) ? true : false;
}

bool backchk2() {
    int d = robotd;
    int x = robotx - dx[d], y = roboty - dy[d];
    return (map[x][y] == 2) ? true : false;
}

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

    int N, M;
    cin >> N >> M >> robotx >> roboty >> robotd;
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < M;j++) {
            int x; cin >> x;
            map[i][j] = x;
        }
    }
    map[robotx][roboty] = 2;
    while (true) { // 이 반복문은 반드시 끝나므로 이렇게 코딩할 수 있다
        if (leftchk()) {
            robotd -= 1;
            if (robotd < 0) robotd += 4;
            robotx += dx[robotd], roboty += dy[robotd];
            map[robotx][roboty] = 2;
        }
        else if (backchk1()) {
            robotd += 2;
            if (robotd > 3) robotd -= 4;
            robotx += dx[robotd], roboty += dy[robotd];
            map[robotx][roboty] = 2;
        }
        else if (rightchk()) {
            robotd += 1;
            if (robotd > 3) robotd -= 4;
            robotx += dx[robotd], roboty += dy[robotd];
            map[robotx][roboty] = 2;
        }
        else if (frontchk()) {
            robotx += dx[robotd], roboty += dy[robotd];
            map[robotx][roboty] = 2;
        }
        else if (backchk2()) {
            robotx -= dx[robotd], roboty -= dy[robotd];
        }
        else break;
    }
    int cnt = 0;
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < M;j++) {
            if (map[i][j] == 2) cnt++;
        }
    }
    cout << cnt;

    return 0;
}