[BOJ/Gold 3] 백준 31404 아리스, 청소합니다! (Easy)(C++)

문제 링크

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

31404번: 아리스, 청소합니다! (Easy)

 

문제

뽜밤뽜밤-! 아리스는 메이드 용사로 전직했습니다!

 

밀레니엄 사이언스 스쿨 엔지니어부의 히비키는 튜링 머신과 비슷한 원리로 작동하는 로봇 청소기를 발명했습니다.

히비키는 로봇 청소기로 H × W 직사각형 격자 모양의 게임개발부 부실을 청소하려고 합니다. 격자칸의 좌표는 (r, c)로 나타낼 수 있으며, 아래로 갈수록 r이 증가하고 오른쪽으로 갈수록 c가 증가합니다. 가장 왼쪽 위 칸의 좌표는 (0, 0), 오른쪽 아래 칸의 좌표는 (H−1, W−1)입니다.

처음에 모든 칸은 먼지로 뒤덮여 있습니다. 로봇 청소기는 격자 한 칸 크기이며, 바라보는 방향으로 전진하거나 제자리에서 회전할 수 있습니다.

로봇 청소기의 전원을 켜면 다음과 같이 작동합니다. 먼저 H × W 크기의 규칙표 A와 B를 만듭니다. 규칙표의 각 칸은 청소할 영역의 격자칸에 대응됩니다. 규칙표에는 회전 각도가 적혀 있습니다.

이후 로봇 청소기는 매 단위 시간마다 다음과 같은 이동을 반복합니다.

• 현재 칸에 먼지가 있다면 먼지를 제거합니다.
• 방금 먼지를 제거했다면 규칙표 A를, 먼지를 제거하지 않았다면 규칙표 B를 참조합니다. 규칙표에서 현재 좌표에 적힌 만큼 시계방향으로 회전합니다.
• 바라보는 방향으로 한 칸 전진합니다.

 

이동을 마친 후에, 로봇 청소기가 영역 밖으로 벗어났다면 작동을 중지합니다. 또한, 지금부터 위의 과정을 아무리 반복해도 더이상 먼지를 제거할 수 없는 경우에도 작동을 중지합니다.

메이드 용사로 전직한 아리스는 히비키의 로봇청소기를 보고, 용사 수행을 위해 로봇 청소기와 똑같은 원리로 동작하여 게임개발부 부실을 청소하려고 합니다. 방의 구조와 아리스의 처음 위치, 그리고 규칙표가 주어집니다. 아리스가 청소를 시작하고 마칠 때까지 이동한 횟수를 출력하세요.

 

입력

첫 번째 줄에 방의 크기를 나타내는 H, W가 주어집니다. (1 ≤ H, W ≤ 64)

두 번째 줄에 아리스의 처음 위치를 나타내는 R, C, D가 주어집니다. 아리스의 좌표는 (R, C)이고, 위쪽을 기준으로 시계방향으로 90D도만큼 회전한 방향을 바라보고 있음을 나타냅니다. (0 ≤ R <H; 0 ≤ C <W; 0 ≤ D ≤ 3)

다음 H개의 줄에 규칙표 A가 주어집니다.

다음 H개의 줄에 규칙표 B가 주어집니다.

규칙표는 길이 W인 문자열 H개로 주어집니다. 문자열은 0 이상 3 이하의 숫자로 구성되며, 숫자 d는 90d도 회전을 의미합니다.

 

출력

아리스가 청소를 시작하고 마칠 때까지 이동한 횟수를 출력하세요.

 

예제 입력 1

3 4
1 3 0
1122
1003
3330
1200
3031
3332

예제 출력 1

13

 

예제 1의 규칙표는 다음과 같습니다.

 

 

아리스는 아래 그림과 같은 순서로 이동합니다. 아리스가 13회 이동하고 나면, 더이상 이동을 반복해도 계속해서 먼지가 없는 칸만 방문하므로 청소를 중지합니다.

 

 

예제 입력 2

3 4
1 3 0
1122
1003
3330
1200
1031
3332

예제 출력 2

9

 

 

예제 2의 규칙표는 다음과 같습니다.

 

 

아리스는 아래 그림과 같은 순서로 이동합니다. 아리스가 9회 이동하고 나면, 더이상 이동을 반복해도 먼지를 제거하지 못한 채 영역 밖으로 벗어나므로 청소를 중지합니다.

 

 

알고리즘 분류

• 구현

 

풀이

먼지가 없는 칸을 탐색할 때가 중요하다.

영역 안의 먼지가 없는 특정한 칸을 특정한 방향을 통해서 방문한 적이 없는 경우 해당 칸을 특정한 방향을 통해서 방문했음을 기록하고, 먼지가 없는 칸을 방문한 횟수를 1회 증가시킨다.

다음 칸은 규칙표 B를 바탕으로 방향을 변경해서 이동하는데, 영역 밖을 벗어난 경우 아리스가 최종적으로 이동할 횟수는 총 이동 횟수에서 마지막으로 청소한 후 먼지가 없는 칸을 방문한 횟수를 뺀 값과 같다.

영역 안에 있는 칸임에도 불구하고 이미 해당 칸을 동일한 방향을 통해서 방문했다면 이제부터는 추가로 이동해도 더 이상 청소할 칸을 방문할 수 없게 되므로 이 때에도 아리스가 최종적으로 이동할 횟수는 총 이동 횟수에서 마지막으로 청소한 후 먼지가 없는 칸을 방문한 횟수를 뺀 값이 된다.

 

먼지가 있는 칸을 방문한 경우, 먼지가 없는 칸을 특정한 방향을 통해서 방문했음을 기록한 내용을 전부 초기화한다. 그리고 해당 칸의 먼지를 제거했음을 기록하고 규칙표 A를 바탕으로 방향을 변경한다.

먼지 제거 후 다음으로 이동할 칸이 영역 밖이라면 아리스가 최종적으로 이동할 횟수는 총 이동 횟수와 동일하다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 65
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int H, W, R, C, D;
int MAP[MAX][MAX], A[MAX][MAX], B[MAX][MAX];
bool Visited[MAX][MAX][4];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,1,0,-1 };
int Answer;

void input() {
    cin >> H >> W;
    cin >> R >> C >> D;
    for (int i = 0; i < H; i++) {
        string S;
        cin >> S;
        for (int j = 0; j < W; j++) {
            A[i][j] = (S[j] - '0');
        }
    }
    for (int i = 0; i < H; i++) {
        string S;
        cin >> S;
        for (int j = 0; j < W; j++) {
            B[i][j] = (S[j] - '0');
        }
    }
}

void init_Position() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = 0; k < 4; k++) {
                Visited[i][j][k] = false;
            }
        }
    }
}

void settings() {
    queue<pair<pair<int, int>, pair<int, pair<int, int> > > > Q;
    Q.push(make_pair(make_pair(R, C), make_pair(D, make_pair(0, 0))));

    while (!Q.empty()) {
        int NowY = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowD = Q.front().second.first;
        int NowT = Q.front().second.second.first;
        int NowC = Q.front().second.second.second;
        Q.pop();

        if (MAP[NowY][NowX] == 0) {
            MAP[NowY][NowX] = 1;
            init_Position();
            int NextD = ((NowD + A[NowY][NowX]) % 4);
            int NextY = NowY + MoveY[NextD];
            int NextX = NowX + MoveX[NextD];
            if ((NextY < 0) || (NextY >= H) || (NextX < 0) || (NextX >= W)) {
                Answer = (NowT + 1);
                return;
            }
            Q.push(make_pair(make_pair(NextY, NextX), make_pair(NextD, make_pair(NowT + 1, 0))));
        }
        else {
            if (!Visited[NowY][NowX][NowD]) {
                Visited[NowY][NowX][NowD] = true;
                int NextD = ((NowD + B[NowY][NowX]) % 4);
                int NextY = NowY + MoveY[NextD];
                int NextX = NowX + MoveX[NextD];
                if ((NextY < 0) || (NextY >= H) || (NextX < 0) || (NextX >= W)) {
                    Answer = (NowT - NowC);
                    return;
                }
                Q.push(make_pair(make_pair(NextY, NextX), make_pair(NextD, make_pair(NowT + 1, NowC + 1))));
            }
            else {
                Answer = (NowT - NowC);
                return;
            }
        }
    };
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}