문제

14503 - 로봇 청소기

풀이

청소기 로직

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
   a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

쉽게 풀어내보자

먼저 청소기는 북쪽을 바라보고 있다고 가정하자.

1. 현재 위치를 청소하자.

2. a나 b를 처리하기 전에 동서남북 모두 청소를 안했는지 확인하자.

   • 청소를 안한 곳이 없다면? -> 후진하자.
     • 후진하고 봤더니 벽이라면? -> 청소 종료(종료 조건).
     • 후진하고 봤더니 벽이 아니라면? -> 1번으로 돌아가자.

3. 서쪽 방향이 청소가 안되어있다면? -> 서쪽 방향으로 한 칸 이동하고 청소하자 -> 1번으로 돌아가자.

4. 서쪽 방향이 이미 청소가 되어있다면? -> 서쪽 방향으로 돌기만 하자. -> 1번으로 돌아가자.

알고리즘

초기 세팅

1. 편의상 문제에서의 변수들을 아래와 같이 이름 짓자.

   • r => y, c => x, d => dir

2. vector<vector<int>> room 배열에 청소할 공간의 정보를 입력받자.

3. 방향에 따른 청소기가 전진할 값을 세팅하자.
   ex) dir=0 일 때, 청소기는 room[y+dy[0]][x+dx[0]] 을 청소한다.

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

4. 방향에 따른 청소기가 후진할 값도 세팅하자.

    int back_dy[] = {1, 0, -1, 0};
    int back_dx[] = {0, -1, 0, 1};

다음으로 청소할 공간을 체크할 함수

// 다음으로 청소할 공간 체크
bool CanGo(int y, int x, const vector<vector<int>> &room)
{
    // 청소가 안되어 있다면 true
    if (room[y][x] == 0)
        return true;
    // 청소가 되어있거나 벽이라면 false
    else
        return false;
}

청소기 로직

    while (true)
    {
        //현재 위치 청소
        room[y][x] = 2;

        // 동서남북이 모두 청소 전인지 체크
        bool isAllCleaned = true;
        for (int i = 0; i < 4; i++)
            if (room[y + dy[i]][x + dx[i]] == 0)
                isAllCleaned = false;

        // 모두 청소가 되어있다면
        if (isAllCleaned)
        {
            // 후진
            y = y + back_dy[dir];
            x = x + back_dx[dir];

            // 후진하고 보니 벽이라면 종료
            if (room[y][x] == 1)
                break;
            // 벽이 아니라면 1번 조건으로 돌아가자
            else
                continue;
        }

        // 방향에 따른 청소기의 다음 목적지를 임시 세팅
        int nextY = y + dy[dir];
        int nextX = x + dx[dir];

        // 전진이 가능하다면
        if (CanGo(nextY, nextX, room))
        {
            // 청소기의 다음 목적지 세팅
            y = nextY;
            x = nextX;
        }

        // 왼쪽으로 방향 변경: 북 -> 서 -> 남 -> 동 -> 북 -> ...
        if (dir == 0)
            dir += 3;
        else
            dir--;
    }

코드

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

int N, M;
int y, x, dir;

bool CanGo(int y, int x, const vector<vector<int>> &room)
{
    if (room[y][x] == 0)
        return true;
    else
        return false;
}

void Solve(vector<vector<int>> &room)
{
    int dy[] = {0, -1, 0, 1};
    int dx[] = {-1, 0, 1, 0};

    int back_dy[] = {1, 0, -1, 0};
    int back_dx[] = {0, -1, 0, 1};

    while (true)
    {
        room[y][x] = 2;

        bool isAllCleaned = true;
        for (int i = 0; i < 4; i++)
            if (room[y + dy[i]][x + dx[i]] == 0)
                isAllCleaned = false;

        if (isAllCleaned)
        {
            y = y + back_dy[dir];
            x = x + back_dx[dir];

            if (room[y][x] == 1)
                break;
            else
                continue;
        }

        int nextY = y + dy[dir];
        int nextX = x + dx[dir];

        if (CanGo(nextY, nextX, room))
        {
            y = nextY;
            x = nextX;
        }

        if (dir == 0)
            dir += 3;
        else
            dir--;
    }

    int answer = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (room[i][j] == 2)
                answer++;

    cout << answer;
}

int main()
{
    cin >> N >> M;
    cin >> y >> x >> dir;

    vector<vector<int>> room(N, vector<int>(M));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> room[i][j];

    Solve(room);
}

주석코드

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

int N, M;
int y, x, dir;

// 다음으로 청소할 공간 체크
bool CanGo(int y, int x, const vector<vector<int>> &room)
{
    // 청소가 안되어 있다면 true
    if (room[y][x] == 0)
        return true;
    // 청소가 되어있거나 벽이라면 false
    else
        return false;
}

void Solve(vector<vector<int>> &room)
{
    // 0: 북, 1: 동, 2: 남, 3: 서

    // 방향에 따른 청소기의 전진
    int dy[] = {0, -1, 0, 1};
    int dx[] = {-1, 0, 1, 0};

    // 방향에 따른 청소기의 후진
    int back_dy[] = {1, 0, -1, 0};
    int back_dx[] = {0, -1, 0, 1};

    while (true)
    {
        //현재 위치 청소
        room[y][x] = 2;

        // 동서남북이 모두 청소 전인지 체크
        bool isAllCleaned = true;
        for (int i = 0; i < 4; i++)
            if (room[y + dy[i]][x + dx[i]] == 0)
                isAllCleaned = false;

        // 모두 청소가 되어있다면
        if (isAllCleaned)
        {
            // 후진
            y = y + back_dy[dir];
            x = x + back_dx[dir];

            // 후진하고 보니 벽이라면 종료
            if (room[y][x] == 1)
                break;
            // 벽이 아니라면 1번 조건으로 돌아가자
            else
                continue;
        }

        // 방향에 따른 청소기의 다음 목적지를 임시 세팅
        int nextY = y + dy[dir];
        int nextX = x + dx[dir];

        // 전진이 가능하다면
        if (CanGo(nextY, nextX, room))
        {
            // 청소기의 다음 목적지 세팅
            y = nextY;
            x = nextX;
        }

        // 왼쪽으로 방향 변경: 북 -> 서 -> 남 -> 동 -> 북 -> ...
        if (dir == 0)
            dir += 3;
        else
            dir--;
    }

    // 청소한 공간 갯수 검사
    int answer = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (room[i][j] == 2)
                answer++;

    cout << answer;
}

int main()
{
    cin >> N >> M;
    cin >> y >> x >> dir;

    vector<vector<int>> room(N, vector<int>(M));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> room[i][j];

    Solve(room);
}